Multi-label Ranking from Positive and Unlabeled Data
Atsushi Kanehira and Tatsuya Harada
The University of Tokyo
7-3-1 Hongo Bunkyo-ku, Tokyo, Japan{kanehira, harada}@mi.t.u-tokyo.ac.jp

Abstract
In this paper, we specifically examine the training of amulti-label classifier from data with incompletely assigned
labels. This problem is fundamentally important in many
multi-label applications because it is almost impossible forhuman annotators to assign a complete set of labels, although their judgments are reliable. In other words, a multilabel dataset usually has properties by which (1) assigned
labels are definitely positive and (2) some labels are absent but are still considered positive. Such a setting has
been studied as a positive and unlabeled (PU) classification problem in a binary setting. We treat incomplete label
assignment problems as a multi-label PU ranking, which isan extension of classical binary PU problems to the wellstudied rank-based multi-label classification. We derive theconditions that should be satisfied to cancel the negative effects of label incompleteness. Our experimentally obtained
results demonstrate the effectiveness of these conditions.

1. Introduction
Multi-label classification treats a problem that allows
samples to take more than one label. Although the simplest
solution for multi-label classification is training an independent classifier per class, a trained model is well known tohave low classification performance when there is a correlation between classes [7]. For this reason, a multi-label
learning method, which incorporates label dependency, isneeded. In recent years, many studies have specifically addressed multi-label learning [7], [19], [6]. Furthermore,
there are widely diverse applications in many domains including computer vision [5], [27], [18].
To collect a dataset for multi-label classification, researchers generally use crowdsourcing. An alternative is
to collect data in a semi-automatic way as in [26]. In mostcases, the obtained labels will be incomplete but reliable because it is almost impossible to assign a full set of labels to
describe images completely in the real world. For instance,
let us consider the case in which human annotators attach

3%&$.,-$&%%%#'45&"-6%
3%'#7",5$&%#'45&"-6%!"#$!%&'()%*+",-%!"#$!%*"-)%-'"&%!"#$!%&'()%#"!!%!"#$%&"'()*%&"!"#$!%.'/"%-''2!"#$!%.'/"%
01

Figure 1. Multi-label dataset tends to have partially labeled samples. Absent labels are regarded as negative, and it affects classification performance.

labels to the leftmost image in Fig. 1. They might identify ”dog” and ”chair,” and then assign them because they
are the main components. However, besides these, ”sofa,””carpet,” and ”box” can also be used. In addition, numerous
other possible correct answers exist such as scene, breed ofdog, and attribute.
As in the example presented above, the obtained dataset
has properties by which (1) assigned labels are definitely
positive and (2) absent labels are not necessarily negative.
Because conventional multi-label learning models ignore
this incompleteness and because they regard unlabeled objects as negative, their performance will be affected as in thecase of the right-hand side of Fig. 1. Therefore, an incomplete label assignment problem is fundamentally importantand critical in multi-label learning, which should be solved.
Our goal in this paper is to propose a method that enables
us to train a classifier consistently from data with incompletely assigned labels. We deal with the setting as follows:
1. Assigned labels are definitely positive.
2. Absent labels are not necessarily negative.

3. Lastly, samples are allowed to take more than one label.
Settings (1) and (2) have been studied as positive and unlabeled (PU) classification problems in a binary case [15],[22]. Moreover, setting (3) is a multi-label classification
setting. In this work, we deal with a multi-label PU ranking problem to treat the setting, which includes all of (1),(2), and (3); then, by extending an analysis for binary PU
classification [10] to a multi-label problem, we derive theconditions under which the loss function should be satisfied
to have consistency even if assigned labels are incomplete.
The main contributions of this work are as follows:

studies have addressed this problem [22]. Actually, [15]constructed a probabilistic model only from observablesamples and estimated a proper classifier using it. In addition, [10] analyzed a binary PU classification problem andrevealed that PU classification can be cast as a cost-sensitive
learning, which changes the weight of the penalty per class.
Using a symmetric non-convex function as a surrogate loss
makes it possible to learn consistently. However, these studies emphasized only binary classification problems and did
not assume that samples take more than one label.

1. We derive the conditions that should be satisfied tocancel the negative effects of label incompleteness in
multi-label PU ranking.

Some works have attempted to address label incompleteness in multi-label learning as label deficits. [3] tried toeliminate the influence of label deficits in the optimization
process by adding a regularization term to rank loss, which
forces the difference between scores for positive and negative labels to be group sparse. Then, [20] extended [15] toa multi-label setting by considering the label dependency.
[28] dealt with weak labels in a multiple-instance, multilabel learning setting. Subsequently, [23] used a conditional
restricted Boltzmann machine to denoise the label deficit.
However, these studies did not mention that the condition
loss function should be satisfied.

2. We demonstrate the effectiveness of these conditions
using experiments on several multi-label datasets.
In Sec.1, we describe the goals and contributions of thiswork. We then discuss related works in Sec. 2. In Sec.
3, we describe the settings of multi-label rankings. In Sec.
4, we explain an extension of the analyses for binary PU
to multi-label problems and describe the conditions underwhich the loss function is satisfied. Several experimentson synthetic datasets and image annotation datasets are explained in Sec. 5 to investigate the efficacy of the derived
conditions. Experimental results are discussed in Sec. 6.
Then, we conclude our work in Sec. 7.

2. Related work
2.1. Multi-label ranking
Multi-label classification problems have been studied inrecent years. One of the most common approaches is basedon label ranking. Label ranking is aimed at ranking all positive classes higher than negative ones by minimizing rank
loss. Rank loss, originally proposed by [13], has been studied well [16]. Actually, [9] relaxed the constraint condition
to allow the application of the algorithm to large-scale data.
In the computer vision domain, many algorithms have been
proposed based on label ranking. [27] proposed a learning model, WSABIE, that embeds image and word features
to a common space by optimizing the weighted rank loss.
[4], [1] used rank loss for the object recognition task. In
addition, [17] trained a deep convolutional neural network
for a multi-label task by replacing the softmax loss with theweighted rank loss proposed by [27]. However, all of theseworks assume that all labels are assigned completely and do
not deal directly with label incompleteness.

2.2. PU Classification
The problem of training classifiers from positive samples
and unlabeled samples is called PU classification. Some

2.3. Learning from incompletely labeled data

3. Multi-label ranking
In this section, we describe the setting of the multi-label
ranking problem. Let X be a sample space and Y={0,1}m
be the possible set of labels, where m denotes the number ofclasses. yi denotes the status of the sample in terms of thei-th class: if yi =1, then the i-th class is positive for a given
sample, and if yi =0, then it is negative. A dataset having N samples S={(x1 ,y1 ),(x1 ,y1 ),...,(xN ,yN )} is generated from an unknown distribution on X ⇥Y. A scorefunction is defined as f (x)=(f1 (x),f2 (x),...,fm (x)) : X !
Rm . In an empirical risk minimization framework, algorithms are used to minimize the expectations of the loss
function over the (sample, label) space. In other words, thefollowing f ⇤ =argmin L(f ) is computed:L(f ) =Exy [L(f (x),y)].

(1)

L(f (x),y) indicates the loss function that takes a label and ascore for the sample as input. Although some loss functions
including 0-1 subset loss and Hamming loss are proposed,
we treat the rank loss, which is commonly used in multilabel learning.

3.1. Rank loss
Rank loss imposes a penalty on a classifier when a pairof labels is incorrectly ranked. It can be defined as follows:X
1
Lrank (f (x),y) =[[fi <fj ]]+ [[fi =fj ]], (2)2{i,j:y =1,y =0}ijwhere i,j are the indices of the class. The i-th element off (x), which means the score for the i-th class, is denotedby fi , omitting the dependency for x. [[·]] is the indicatorfunction that takes a value of 1 when the conditions inside
the brackets are met; otherwise, it is 0. From (1), the loss
function that should be minimized is
Lrank = Exy [Lrank (f (x),y)]X=
P (y)Ex|y [Lrank (f (x),y)]
y2Y

X

X

j

By swapping two summations, we can rewrite (3) as

=

Lrank
X


1
P (yi =1,yj =0)Ex|yi =1,yj =0 [[fi <fj ]]+ [[fi =fj ]] .
2
{i,j:y =1,y =0}
i

j

(4)

Here, we define the mis-rank rate as1
R(i,j) = Ex|yi =1,yj =0 [[fi <fj ]]+ [[fi =fj ]]2
1= P (fi <fj | yi =1, yj =0)+ P (fi =fj | yi =1,yj =0).
2
(5)
The mis-rank rate R(i,j) is the probability that the computed score of a sample for the positive label is smaller
than that for the negative label. Using this, we express therank loss Lrank as
Lrank ==XX

2. Applying a surrogate loss for optimization with incompletely labeled data leads to error from a correct one,which can be cancelled by selecting a symmetric surrogate loss function such as a ramp loss or a sigmoid
loss.

4.1. Appropriately weighted cost



1
=
P (y)
Ex|y [[fi <fj ]]+ [[fi =fj ]] . (3)2y2Y{i,j:y =1,y =0}i

1. A multi-label PU ranking problem can be cast as a
cost-sensitive learning using positive and unlabeleddata.

P (yi =1,yj =0)R(i,j){i,j:yi =1,yj =0}

P (yi =1,yj =0)R(i,j)+P (yi =0,yj =1)R(j,i).

1i<jm(6)

We can consider rank loss Lrank as the expectation of the
mis-rank rate R(i,j) over all possible pairs of labels. Ourinterest is to minimize it in the PU setting.

4. Multi-label PU ranking
As described above, multi-label PU ranking is a problemof training a label-ranking-based multi-label classifier froma dataset, which has properties in which (1) labels assigned
to samples are definitely positive and (2) absent labels are
not necessarily negative.
In this section, we extend the analysis for binary PU classification [10] to a multi-label setting and derive the following:

In this section, we explain how a multi-label PU ranking problem can be cast as a cost-sensitive learning, whichmeans that we should weight the loss function appropriately. Cost-sensitive learning [14] is a type of learning
method that incorporates the mis-classification cost. Costsensitive “ranking” using rank loss is given naturally as

=

Lrank
X

cij P (yi =1,yj =0)R(i,j)+cji P (yi =0,yj =1)R(j,i).

1i<jm(7)
where cij is the weight of the penalty for mis-ranking forthe pair yi =1,yj =0. We aim at minimizing (6) with incompletely labeled samples. In our PU setting, the mis-rank
rate R(i,j) in (6) cannot be estimated directly from the data
because there are no negative labels. For this reason, we introduce a pseudo-mis-rank rate RX (i,j), which can be estimated from the data, and then consider the optimization of(6) via this quantity. Here, we define the pseudo-mis-rank
rate RX (i,j) as
RX (i,j)1=P (fi <fj | si =1,sj =0)+ P (fi =fj | si =1,sj =0). (8)2Therein, si 2{0,1} shows whether the label of the i-th classis assigned or not. si =1 and si =0 respectively mean thatthe i-th class is labeled and not labeled. The pseudo-misrank rate RX (i,j) represents the possibility that the ranking
score of a sample for an assigned label is smaller than thatfor an absent label. We can estimate this quantity from incompletely labeled data. If we ignore label incompleteness,then the expected loss as actually minimized is not (6) butL̂rankX=
P (si =1,sj =0)RX (i,j)+P (si =0,sj =1)RX (j,i).
1i<jm(9)

Similarly to [10], we assume that unlabeled data are generated from a marginal distribution. This is called the “casecontrolled” setting in PU classification [25]. This conditionis expressed as P (yi =1|si =0)=P (yi =1). Furthermore,we make the assumption that the deficit of a positive label is not biased on the sample space. This condition isrepresented as P (x|si =1)=P (x|yi =1). By these assumptions, the pseudo-mis-rank rate RX (i,j) can be written using R(i,j) as follows (see Appendix A):
RX (i,j)=(1 ⇡ij )R(i,j)+⇡ij R-X (i,j),

(10)

where
R-X (i,j)
1=P (fi <fj | yi =1,yj =1)+ P (fi =fj | yi =1,yj =1),
2
(11)
and
⇡ij =P (yj =1 | yi =1).

(12)

R-X (i,j) denotes the penalty imposed on mistakes attributable to the existence of positive labels contained inabsent labels. To be more specific, in the case of learning from samples with incompletely assigned labels, rank
loss imposes a penalty not for (positive, negative) but for(assigned, not assigned) label pairs. However, these pairs
contain (positive, positive) pairs, which should not be included in the penalty. Here, we represent this excessively
imposed penalty and its ratio as R-X (i,j) and ⇡ij , respectively. Therefore, (10) can be interpreted as a decomposition into two losses: the loss that should be given and theloss that should not be given. Transforming (10), we obtain
R(i,j)=

1(RX (i,j) ⇡ij R-X (i,j)).
1 ⇡ij

(13)

R-X (i,j)+R-X (j,i)
=1,

(14)

we can obtain the following equation (see Appendix B):
LrankX= P (yi =1)RX (i,j)+P (yj =1)RX (j,i) P (yi =1,yj =1)
X= cij P (si =1,sj =0)RX (i,j )+cji P (si =0,sj =1)RX (j,i)(15)

P (yi =1,yj =1).

Here,
cij =

P (yi =1).
P (si =1,sj =0)

minimized. P (si =1,sj =0) is the ratio of the samples in adataset that meets the condition si =1,sj =0. This can be
estimated from the training dataset. In addition, P (yi =1)
can be estimated using the methods proposed in [11], [2].

4.2. Symmetric surrogate loss
In this section, we derive the condition for surrogate loss
used in the optimization process. Mis-rank rate R can be
written as the expectation of the 0-1 function over the sample space as described below:

R(i,j)=Ex|yi =1,yj =0 [l0-1 (fiSimilarly,

8><1 (if x<0)fj )], l0-1 (x)= 12 (if x=0)>:0 (otherwise)

RX (i,j)=Ex|si =1,sj =0 [l0-1 (fi fj )].

By substituting this into (6) and using the relation=P (fi >fj or fi =fj or fi <fj | yi =1,yj =1)

Figure 2. (a) Ramp loss (red dashed line) and sigmoid loss (bluesolid line) meet the described condition, while (b) exponential loss
(red dashed line) and hinge loss (blue solid line) do not.

(16)

Compared with (9), the multi-label PU ranking problem canbe cast as a cost-sensitive learning. In fact, minimizing therank loss function weighted by cij with incompletely labeled data implies that the rank loss with completely labeled data, which should be originally minimized, can be

Because direct optimization of this expectation including
the 0-1 loss is intractable, the surrogate loss function l0 (x)is generally used instead of the 0-1 loss. For example, thepseudo-mis-rank rate is written as follows by applying thehinge loss function l0 H , which is used in many popular models (e.g., support vector machines), as the surrogate loss.
00

RX (i,j)⇡Ex|si =1,sj =0 [l H (fi fj )], l H (x)=(1 x (if x<1)
0 (otherwise)

When fully labeled data are used, by applying surrogate loss
to rank loss (6), we obtain
L0 rankX= P (yi =1,yj =0)Ex|yi =1,yj =0 [l0 (fi fj )]+P (yi =0,yj =1)Ex|yi =0,yj =1 [l0 (fj fi )].

(17)

By replacing RX in (15) with the expectation of surrogate
loss,

Table 1. Methods used in the experiments. Each method corresponds to whether condition 1 (use of weighted loss function) andcondition 2 (use of symmetric loss function) are met or not.

00

L rankX= P (yi =1)Ex|si =1,sj =0 [l0 (fi fj )]Baseline+P (yj =1)Ex|si =0,sj =1 [l0 (fj fi )] P (yi =1,yj =1)
X= P (yi =1,yj =0)Ex|yi =1,yj =0 [l0 (fi fj )]Condition 1(weighted loss)
Condition 2(symmetric loss)+P (yi =0,yj =1)Ex|yi =0,yj =1 [l0 (fj fi )]P (yi =1,yj =1) 1 Ex|yi =1,yj =1 [l0 (fi fj )+l0 (fj fi )](18)
is obtained. From the two equations (17) and (18), we observe the relation L00 rank =L0 rank +(Error). It means thatutilizing surrogate loss in the optimization process with incompletely labeled data causes an error. If we select the surrogate loss function l0 (·) to meet l0 (fi fj )+l0 (fj fi )=1,
then this error is cancelled and L00 rank =L0 rank is obtained.
Convex functions such as hinge loss and exponential loss
(Fig. 2(b)) do not meet this condition. Symmetric nonconvex functions such as ramp loss and sigmoid loss (Fig.
2(a)) satisfy it.
For example, let us consider a case in which data
are completely labeled and separable. In other words,
min Lrank =0. In this case,argmin L0 rank-hinge =argmin L0 rank-ramp .
Completely identical hyperplanes are obtained for both theramp loss and the hinge loss. Considering the PU setting,from the discussion presented above, we obtainargmin L00 rank-ramp =argmin L0 rank-ramp .
On the other hand,argmin L00 rank-hinge 6=argmin L0 rank-hingeThis relation indicates that the obtained boundary differsfrom the optimal one when using hinge loss.

5. Experiment
To investigate the efficacy of the conditions stated in
the previous section, we conducted experiments on threedatasets: synthetic dataset, MSCOCO [24], and NUSWIDE [8].

5.1. Setting
Classifiers were trained from data containing a deficit on
positive labels at a rate from 0% to 80%. The accuracy wasevaluated on fully labeled data. The label deficit is given
from the following steps:
1. Determine the total number of deficit labels Nnoise bymultiplying the deficit rate by the total number of positive labels.

Method 1

Method 2

X

Method 3(proposed)
X

X

X

c
2. Determine the number of deficit samples Nnoiseforclass c P
from a multinomial distribution to meetc
Nnoise = c Nnoise.
c
3. Choose Nnoise samples labeled as c at random and remove their label.

We used the mean average precision in terms of samples as an evaluation criterion. Through all the experiments,
hinge loss and ramp loss were used in the non-symmetricand symmetric surrogate loss function, respectively. Score
functions were linear, and their weights were updated using
stochastic gradient descent. SpecificallyPfor the score function f (x)=WT x and loss function N1 N
n=1 l(f (xn ),yn ),models were updated as
W(t+1) =W(t) ⌘ (⌧ )@l(f (xn ),yn ),@Wwhere N denotes the number of training samples, and ⌘ (⌧ )and ⌧ denote the learning rate and the number of iterations,
respectively. In thisp experiment, we reduced the learning
rate as ⌘ (⌧ ) =⌘ (0) / ⌧ .

5.2. Synthetic dataset
A synthetic dataset was generated as in the following
procedure, which was performed for each sample:
1. The number of relevant labels n is sampled from a
Poisson distribution.
2. For n times, relevant class c is sampled from a multinomial distribution.
3. The number of feature samplings k is sampled from a
Poisson distribution.
4. For k times, feature x is sampled from a multinomial
distribution parametrized per class and their summation is used as a feature of the sample.
Ten thousand samples were generated and then divided
into 8,000 for training and 2,000 for testing. The parameters of the multinomial distributions were sampled froma uniform distribution. In addition, L2 normalization wasapplied to all samples.
Experiment A. First, to show the influence of the derived condition on classification accuracy, we evaluated four
methods, corresponding to whether condition 1 (use of appropriately weighted loss function) and condition 2 (use of

Figure 3. Results of Experiment A on a synthetic dataset. Each figure from the left corresponds to a different mean number of labels (2, 4,
8, 12, 16, 32). The method that meets both conditions has robustness to the label deficit.

symmetric loss function) are met or not (Table 1). In thisexperiment, the prior P (yi =1) in (16) was given from fullylabeled training samples. We fixed the number of classes to
40 and the dimension of a feature to 100. The mean numberof labels for each sample was chosen from (2,4,8,12,16,32).
The result is presented in Fig. 3. In all settings, Method 3,
which satisfies both conditions, could learn most robustly.
As the number of labels increased, the difference in accuracy between Method 3 and the other methods became
large.
Experiment B. Then, we evaluated the accuracy of
Method 3 when combined with prior estimation, which isnecessary for application to a real problem. To this end,
we compared three methods: Method 1 (baseline), Method
3 with a prior given from a fully labeled dataset (denoted
as optimal in result), and Method 3 with an estimated prior(denoted as estimated). To estimate class prior P (yi =1) for
class i, we applied [11] based on distribution matching [12]for every class. Because we cannot know negative samples, this algorithm is designed to estimate prior ✓=p(y=1)
by partially matching marginal distribution p(x) and classconditional distribution p(x|y=1) weighted by prior probability. To this end, the algorithm attempts to minimize thePearson (PE) divergence in terms of ✓. Formally, we obtain✓⇤ =argmin PE◆2
Z ✓1✓p(x|y=1)=argmin1 p(x)dx.
2
p(x)

(19)

Instead of a direct minimization of the PE divergence, thetightest lower bound is minimized. For more details, pleasesee [11]. We changed the synthetic dataset from three pointsof view: (1) the number of classes, (2) the number of labels,and (3) the dimension of the features. Each setting is described as follows:• Choose the number of labels from (2, 4, 8), while thenumber of classes and the dimension of the features
are fixed respectively to 80 and 100.
• Choose the number of classes from (40, 80, 160),
while the number of labels and the dimension of thefeatures are fixed respectively to 4 and 100.
• Choose the dimension of the features from (50, 100,150), while the number of classes and the number oflabels are fixed respectively to 80 and 4.
The results of each setting correspond respectively to
Fig. 4, Fig. 5, and Fig. 6. As shown in Fig. 4, when few
labels were assigned for a fixed number of classes (2 labels
out of 80 classes), and when the label deficit rate was low,
the performance of the method with the estimated prior was
high, sometimes even better than that with the optimal prior,and it worsened as the deficit rate increased. The result of
the experiment using samples with more labels (4 labels outof 80 classes) showed that, although the performance was
low when the label deficit rate was low, it was comparable
to the method with the optimal prior as the deficit increased.
If many labels were attached (8 labels out of 80 classes),
the prior estimation failed and high accuracy could not be
achieved. A similar tendency was observed from an experiment in which the number of classes varied (Fig. 5). TheseFigure 4. Results of Experiment B. Each figure from the left corresponds to a different mean number of labels (2, 4, 8).

Figure 5. Results of Experiment B. Each figure from the left corresponds to a different number of classes (40, 80, 160).

results implied that the rate of (the number of labels)/(thenumber of classes) in the data is a key to the success of
our method combined with prior estimation. From the results of the experiment of changing the dimension of thefeatures shown in Fig. 6, it is apparent that the accuracyof the estimated method approached the optimal one as thedimensions increased.

5.3. Image Annotation Dataset
We conducted experiments on the image annotation
datasets MSCOCO [24] and NUS-WIDE [8]. The settingsof each experiment are given as follows:
MSCOCO: This dataset contains segmentation information and captions in addition to object labels. In thisexperiment, we used only images and object tags attachedto them. We eliminated duplicated tags to a single image.
We used 82,783 samples for training and 40,504 samples
for testing. The number of classes was 80. The average
number of labels was 2.95 per sample.
NUS-WIDE : This dataset includes Flickr images with
5,018 types of tags. We used 81 classes predetermined in
the dataset and 161,789 samples for training and 107,859
samples for testing. The average number of labels was 1.76
per sample.
As the image feature, we used the activation of the 7thlayer of AlexNet [21] pre-trained with the ILSVRC2012
dataset. The dimensions of the visual features were 4,096.
We compared the same methods as those used in the previous experiment: Method 1 (baseline), Method 3 (opti-mal), and Method 3 (estimated). In these experiments, weestimated the prior using a naive method, which uses theratio of a labeled sample per class in the training dataset.
The experimental results for MSCOCO and NUS-WIDE
are presented in Fig. 7 and Fig. 8, respectively. In bothdatasets, Method 3 with the estimated prior was able to improve slightly the accuracy in every deficit rate even though
the prior estimation was naive.

6. Discussion
The results of Experiment A on the synthetic dataset
showed that, as both (A) the label deficit rate and (B) the
number of labels assigned to the samples increased, the difference in accuracy between the methods with condition 1(Method 1 and Method 3) and those without it (baseline andMethod 2) increased. This result can be explained using thefollowing analysis. As provided in (9), let L̂rank denote theloss function when we do not change the weight per class.
The error from true loss Lrank L̂rank can be decomposed
into the following: (a) A term proportional to the probability that samples are unlabeled even if they are positive.
(b) A term proportional to the probability that both labels
within a pair of labels are assigned (see Appendix C). (a)and (b) respectively correspond to (A) and (B).
Furthermore, if condition 1 is met, the difference in accuracy between the method with condition 2 and that without
it becomes large when samples have many labels. That result derives from the error caused by surrogate loss in the
PU setting data, where L00 rank L0 rank (provided in (17)and (18)) is proportional to the probability that both labels

Figure 6. Results of Experiment B. Each figure from the left corresponds to a different number of features (50, 100, 150).

Figure 7. Experimental result for the MSCOCO dataset.

are positive from every pair.
The reason for the low performance of Method 1, evenwhen the label deficit rate was low, can be attributed to thefact that an error occurs when the “case-controlled” condition is not satisfied, which we assumed to derive the conditions. In contrast to Method 1, Method 3 still showed
high performance because the error was low when symmetric loss was used. Particularly, when a label’s deficit rate is0%, or the labels are assigned completely, this error can becancelled using symmetric loss (see Appendix D).
In many situations with Experiment B on the synthetic
dataset, the accuracy near a 0% deficit rate was low because
the prior estimation method we used did not assume thatthe labels were complete. Our method works when the label
deficit rate is greater than about 20%, which is likely in realistic data. To treat both complete and incomplete labels using the same method, it is necessary to invent more flexible
prior estimation methods, which is a subject for our future
work. We conjecture that the reason for the prior estimation
failing when numerous labels were attached is that positive
samples and negative samples for one class tend to shareother class’s label, which causes low separability in feature
space. For a task of classifying (dog, cat, human), if wecollect images in which they exist together with high probability, the sample labeled as (cat, human) and (dog, cat,human) might have similar features. The rate of such a sample in a dataset increases as the number of labels increases
for a fixed number of classes. It is extremely difficult toestimate the prior from such low-separability data. The per-Figure 8. Experimental result for the NUS-WIDE dataset.

formance of a method with prior estimation that sometimes
overcomes the optimal one can be thought to estimate the
distribution from which data are generated more accurately
than taking a ratio of the samples in a dataset without a label
deficit.
In the experiments on image annotation datasets, we estimated the class prior in a naive manner because the computational costs of existing algorithms are high. Despite
its simplicity, our method slightly improved the accuracy,
but an efficient estimation algorithm is needed for more improvement when applied to large-scale data.

7. Conclusion
In this paper, we specifically examined the training of amulti-label classifier from incompletely labeled data, whichis essential for multi-label training. Regarding this problem
as a multi-label PU classification problem, we extended thebinary PU classification to label-ranking-based multi-label
learning. By analyzing this problem, we derived two conditions for training classifiers consistently even if only partsof the relevant labels are obtained: (1) use of appropriately
weighted loss function and (2) use of symmetric surrogate
loss. We conducted experiments on several datasets andalso demonstrated the efficacy of these conditions.

8. Acknowledgment
This work was supported by CREST, JST. The authors
would like to thank Prof. Masashi Sugiyama (The University of Tokyo) for the useful discussions.

References[1] Z. Akata, F. Perronnin, Z. Harchaoui, and C. Schmid. Labelembedding for attribute-based classification. In CVPR, 2013.
[2] G. Blanchard, G. Lee, and C. Scott. Semi-supervised novelty detection. The Journal of Machine Learning Research,
11:2973–3009, 2010.
[3] S. S. Bucak, R. Jin, and A. K. Jain. Multi-label learning withincomplete class assignments. In CVPR, 2011.
[4] S. S. Bucak, P. K. Mallapragada, R. Jin, and A. K. Jain. Efficient multi-label ranking for multi-class learning: application to object recognition. In ICCV, 2009.
[5] G. Carneiro, A. B. Chan, P. J. Moreno, and N. Vasconcelos.
Supervised learning of semantic classes for image annotation
and retrieval. PAMI, 29(3):394–410, 2007.
[6] Y.-N. Chen and H.-T. Lin. Feature-aware label space dimension reduction for multi-label classification. In NIPS, 2012.
[7] W. Cheng, E. Hüllermeier, and K. J. Dembczynski. Bayes
optimal multilabel classification via probabilistic classifier
chains. In ICML, 2010.
[8] T.-S. Chua, J. Tang, R. Hong, H. Li, Z. Luo, and Y. Zheng.
Nus-wide: a real-world web image database from national
university of singapore. In CIVR, 2009.
[9] K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and
Y. Singer. Online passive-aggressive algorithms. The Journalof Machine Learning Research, 7:551–585, 2006.
[10] M. C. Du Plessis, G. Niu, and M. Sugiyama. Analysis oflearning from positive and unlabeled data. In NIPS, 2014,
pages 703–711.
[11] M. C. Du Plessis and M. Sugiyama. Class prior estimationfrom positive and unlabeled data. IEICE TRANSACTIONS
on Information and Systems, 97(5):1358–1362, 2014.
[12] M. C. Du Plessis and M. Sugiyama. Semi-supervised learning of class balance under class-prior change by distribution
matching. Neural Networks, 50:110–119, 2014.
[13] A. Elisseeff and J. Weston. A kernel method for multilabelled classification. In NIPS, 2001.
[14] C. Elkan. The foundations of cost-sensitive learning. In IJCAI, 2001.
[15] C. Elkan and K. Noto. Learning classifiers from only positive
and unlabeled data. In SIGKDD, 2008.
[16] W. Gao and Z.-H. Zhou. On the consistency of multi-label
learning. Artificial Intelligence, 199:22–44, 2013.
[17] Y. Gong, Y. Jia, T. Leung, A. Toshev, and S. Ioffe. Deep
convolutional ranking for multilabel image annotation. arXiv
preprint arXiv:1312.4894, 2013.
[18] M. Guillaumin, T. Mensink, J. Verbeek, and C. Schmid.
Tagprop: Discriminative metric learning in nearest neighbormodels for image auto-annotation. In ICCV, 2009.
[19] A. Kapoor, R. Viswanathan, and P. Jain. Multilabel classification using bayesian compressed sensing. In NIPS, 2012.
[20] X. Kong, Z. Wu, L.-J. Li, R. Zhang, P. S. Yu, H. Wu, andW. Fan. Large-scale multi-label learning with incomplete
label assignments. In SIAM, 2014.
[21] A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet
classification with deep convolutional neural networks. In
NIPS, 2012.

[22] W. S. Lee and B. Liu. Learning with positive and unlabeled
examples using weighted logistic regression. In ICML, 2003.
[23] X. Li, F. Zhao, and Y. Guo. Conditional restricted boltzmann
machines for multi-label learning with incomplete labels. In
AISTATS, 2015.
[24] T.-Y. Lin, M. Maire, S. Belongie, J. Hays, P. Perona, D. Ramanan, P. Dollár, and C. L. Zitnick. Microsoft coco: Common objects in context. In ECCV, 2014.
[25] A. Menon, B. V. Rooyen, C. S. Ong, and B. Williamson.
Learning from corrupted binary labels via class-probability
estimation. In ICML, 2015.
[26] L. Von Ahn and L. Dabbish. Labeling images with a computer game. In CHI, 2004.
[27] J. Weston, S. Bengio, and N. Usunier. Wsabie: Scaling up tolarge vocabulary image annotation. In IJCAI, 2011.
[28] S.-J. Yang, Y. Jiang, and Z.-H. Zhou. Multi-instance multilabel learning with weak label. In IJCAI, 2013.

A.

C.

From two conditions P (yi =1|si =0)=P (yi =1) andP (x|si =1)=P (x|yi =1),
P (fi <fj | si =1,sj =0)=P (yj =0 | yi =1,sj =0)P (fi <fj | yi =1,yj =0,sj =0)+P (yj =1 | yi =1,sj =0)P (fi <fj | yi =1,yj =1,sj =0)+P (yj =1 | yi =1)P (fi <fj | yi =1,yj =1).
Similarly,
1
P (fi =fj | si =1,sj =0)2
1= P (yj =0 | yi =1)P (fi =fj | yi =1,yj =0)2
1+ P (yj =1 | yi =1)P (fi =fj | yi =1,yj =1).
2(20)

1i<jm(21)

From (13),P (yi =1,yj =0)R(i,j)⇢
P (yi =1,yj =0)=
RX (i,j) P (yj =1|yi =1)R X (i,j)
P (yj =0|yi =1)(23)

Plugging the equation above and (14) into (6), we obtain

P (si =1,sj =0)RX (i,j)+P (si =0,sj =1)RX (j,i)⇢
P (si =1,sj =1) RX (i,j)+RX (j,i)+P (yi =1,si =0)RX (i,j)+P (yj =1,sj =0)RX (j,i)+const.

(26)

The first term is proportional to the ratio of samples having
both i-th and j-th label. Second and third terms are proportional to ratio of samples, which is not labeled even if they
are positive.

D.

When labels are given completely, the loss function
which should be minimized is (6),
Lrank
X
=
P (yi =1,yj =0)R(i,j)+P (yi =0,yj =1)R(j,i).
1i<jm(27)

However, the loss function derived based on “casecontrolled” assumption is (15)LrankX
= P (yi =1)RX (i,j)+P (yj =1)RX (j,i) P (yi =1,yj =1)(28)

P (yi =1,yj =0)R(i,j)+P (yi =0,yj =1)R(j,i)

Considering the case in which label deficit does not exist,
because R(i,j)=RX (i,j),

P (yi =1)RX (i,j)+P (yj =1)RX (j,i)

Lrank-falseX= P (yi =1)R(i,j)+P (yj =1)R(j,i) P (yi =1,yj =1).
(29)

1i<jm

X

X

=

B.

=

Lrank L̂rankX=
P (yi =1)RX (i,j)+P (yj =1)RX (j,i) const
1i<jm

1=P (fi <fj | si =1,sj =0)+ P (fi =fj | si =1,sj =0)2=(1 ⇡ij )R(i,j)+⇡ij R X (i,j).
(22)=

from (15) and (9), we obtain

X

RX (i,j)

Lrank
X

(25)

=P (yi =1,si =0)+P (si =1,sj =1),

1i<jm

Combining them, we obtain=P (yi =1)RX (i,j) P (yi =1,yj =1)R X (i,j),

P (yi =1) P (si =1,sj =0)=P (yi =1,si =0)+P (yi =1,si =1) P (yi =1,si =1,sj =0)=P (fi <fj | yi =1,sj =0)=P (yj =0 | yi =1)P (fi <fj | yi =1,yj =0)

Because1i<jm⇢
P (yi =1,yj =1) R X (i,j)+R X (j,i)
X=
P (yi =1)RX (i,j)+P (yj =1)RX (j,i)
1i<jm

P (yi =1,yj =1),

(24)

Their mutual difference is
Lrank-false Lrank⇢X= P (yi =1,yj =1) R(i,j)+R(j,i) 1 .

(30)

This error is proportional to the joint probability that bothi-th class and j-th class are positive. However, this error iscancelled if we use symmetric surrogate loss.