Learning from Candidate Labeling Sets

Francesco Orabona
DSI, Università degli Studi di Milano
orabona@dsi.unimi.it

Luo Jie
Idiap Research Institute and EPF Lausannejluo@idiap.ch

Abstract
In many real world applications we do not have access to fully-labeled training
data, but only to a list of possible labels. This is the case, e.g., when learning visualclassifiers from images downloaded from the web, using just their text captions ortags as learning oracles. In general, these problems can be very difficult. However
most of the time there exist different implicit sources of information, coming fromthe relations between instances and labels, which are usually dismissed. In thispaper, we propose a semi-supervised framework to model this kind of problems.
Each training sample is a bag containing multi-instances, associated with a setof candidate labeling vectors. Each labeling vector encodes the possible labels
for the instances in the bag, with only one being fully correct. The use of thelabeling vectors provides a principled way not to exclude any information. We
propose a large margin discriminative formulation, and an efficient algorithm tosolve it. Experiments conducted on artificial datasets and a real-world images andcaptions dataset show that our approach achieves performance comparable to an
SVM trained with the ground-truth labels, and outperforms other baselines.

1 Introduction
In standard supervised learning, each training sample is associated with a label, and the classifier isusually trained through the minimization of the empirical risk on the training set. However, in many
real world problems we are not always so lucky. Partial data, noise, missing labels and other similarcommon issues can make you deviate from this ideal situation, moving the learning scenario fromsupervised learning to semi-supervised learning [7, 26].
In this paper, we investigate a special kind of semi-supervised learning which considers ambiguouslabels. In particular each training example is associated with several possible labels, among which
only one is correct. Intuitively this problem can be arbitrarily hard in the worst case scenario.
Consider the case when one noisy label is consistently appearing together with the true label: in thissituation we could not tell them apart. Despite that, learning could still be possible in many typicalreal world scenarios. Moreover, in real problems samples are often gathered in groups, and the
intrinsic nature of the problem could be used to constrain the possible labels for the samples fromthe same group. For example, we might have that two labels can not appear together in the samegroup or a label can appear only once in each group, as, for example, a specific face in an image.
Inspired by these scenarios, we focus on the general case where we have bags of instances, witheach bag associated with a set of several possible labeling vectors, and among them only one is fully
correct. Each labeling vector consists of labels for each corresponding instance in the bag. For easy
reference, we call this type of learning problem a Candidate Labeling Set (CLS) problem.
As labeled data is usually expensive and hard to obtain, CLS problems naturally arise in many
real world tasks. For example, in computer vision and information retrieval domains, photographs
collections with tags have motivated the studies on learning from weakly annotated images [2], aseach image (bag) can be naturally partitioned into several patches (instances), and one could assume
that each tag should be associated with at least one patch. High-level knowledge, such as spatial
1correlations (e.g. “sun in sky” and “car on street”), have been explored to prune down the labelingpossibilities [14]. Another similar task is to learn a face recognition system from images gatheredfrom news websites or videos, using the associated text captions and video scripts [3, 8, 16, 13].
These works use different approaches to integrate the constraints, such as that two faces in one
image could not be associated with the same name [3], mouth motion and gender of the person [8],or modeling both names and action verbs jointly [16]. Another problem is the multiple annotators
scenario, where each data is associated with the labels given by independently hired annotators. The
annotators can disagree on the data and the aim is to recover the true label of each sample. All these
problems can be naturally casted into the CLS framework.
The contribution of this paper is a new formal way to cast the CLS setup into a learning problem.
We also propose a large margin formulation and an efficient algorithm to solve it. The proposed
Maximum Margin Set learning (MMS) algorithm, can scale to datasets of the order of 105 instances,reaching performances comparable to fully-supervised learning algorithms.
Related works. This type of learning problem dates back to the work of Grandvalet in [12]. Later
Jin and Ghaharmani [17] formalized it and proposed a general framework for discriminative models.
Our work is also closely related to the ambiguous labeling problem presented in [8, 15]. Our framework generalizes them, to the cases where instances and possible labels come in the form of bags.
This particular generalization gives us a principled way for using different kinds of prior knowledge
on instances and labels correlation, without hacking the learning algorithm. More specifically, priorknowledge, such as pairwise constraints [21] and mutual exclusiveness of some labels, can be easily
encoded in the labeling vectors. Although several works have focused on integrating these weaklylabeled information that are complementary to the labeled or unlabeled training data into existingalgorithms, these approaches are usually computational expensive. On the other hand, in our framework we have the opposite behavior: the more prior knowledge we exploit to construct the candidate
set, the better the performance and the faster the algorithm will be.
Other lines of research which are related to this paper are multiple-instance learning (MIL) problems [1, 5, 10], and multi-instance multi-label learning (MIML) problems [24, 25] which extends thebinary MIL setup to multi-labels scenario. In both setups, several instances are grouped into bags,
and their labels are not individually given but assigned to the bags directly. However, contrary to
our framework, in MIML noisy labeling is not allowed. In other words, all the labels being assigned
to the bags are assumed to be true. Moreover, current MIL and MIML algorithms usually rely ona ‘key’ instance in the bag [1] or they transform each bag into single instance representation [25],while our algorithm makes an explicit effort to label every instance in a bag and to consider all ofthem during learning. Hence, it has a clear advantage in problems where the bags are dense in labeled instances and instances in the same bag are independent, as opposed to the cases when several
instances jointly represent a label. Our algorithm is also related to Latent Structural SVMs [22],where the correct labels could be considered as latent variables.

2 Learning from Candidate Labeling Sets
Preliminaries. In this section, we formalize the CLS setting, which is a generalization of theambiguous labeling problem described in [17] from single instances to bags of instances.
In the following we denote vectors by bold letters, e.g. w, y, and use calligraphic font for sets, e.g.,
X . In the CLS setting, the N training data are provided in the form {Xi , Zi }N
i=1 , where Xi is a bag ofdi
Mi instances, Xi = {xi,m }M
,
and
x
∈
R
,
∀
i
=
1,
.
.
.
,
N,
m
=
1,
. . . , Mi . The associated
i,m
m=1
Li
Mi
set of Li candidate labeling vectors is Zi = {zi,l }l=1 , where zi,l ∈ Y , and Y = {1, ..., C}. In
other words there are Li different combinations of Mi labels for the Mi instances in the i-th bag.
We assume that the correct labeling vector for Xi is present in Zi , while the other labeling vectors
maybe partially correct or even completely wrong. It is important to point out that this assumption
is not equivalent to just associating Li candidate labels to each instance. In fact, in this way we also
encode explicitly the correlations between instances and their labels in a bag. For example, consider
a two instances bag {xi,1 , xi,2 }: if it is known that they can only come from classes 1 and 2, andthey can not share the same label, then zi,1 = [1, 2], zi,2 = [2, 1] will be the candidate labelingvectors for this bag, while the other possibilities are excluded from the labeling set. In the following
we will assume that the labeling set Zi is given with the training set. In Section 4.2 we will give apractical example on how to construct this set using the prior knowledge on the task.
2Given the training data {Xi , Zi }N
i=1 , we want to learn a function f (x), to correctly predict theclass of each single instance x, coming from the same distribution. The problem would become
the standard multiclass supervised learning if there is only one labeling vector in every labeling set
Zi , i.e. Li = 1. On the other hand, given a set of C labels, without any prior knowledge, a bagof Mi instances could have maximum C Mi labeling vectors, which becomes a clustering problem.
However, we are more interested in situations when Li ≪ C Mi .
2.1 Large-margin formulation
We introduce here a large margin formulation to solve the CLS problem. It is helpful to first define
by X the generic bag of M instances {x1 , . . . xM }, Z = {z1 , . . . , zL } the generic set of candidate
labeling vectors, and y = {y1 , . . . , yM }, z = {z1 , . . . , zM } ∈ Y M two labeling vectors.
We start by introducing the loss function that assumes the true label ym of each instance xm is
known
M
X
∆(zm , ym ) ,(1)ℓ∆ (z, y) =m=1

where ∆(zm , ym ) is a non-negative loss function measuring how much we pay for having predicted
zm instead of ym . For example ∆(zm , ym ) can be defined as 1(zm 6= ym ), where 1 is the indicatorfunction. Hence, if the vector z is the predicted label for the bag, ℓ∆ (z, y) simply counts the numberof misclassified instances in the bag.
However, the true labels are unknown, and we only have access to the set Z, knowing that the truelabeling vector is in Z. So we use a proxy of this loss function, and propose the ambiguous versionof this loss:ℓAℓ∆ (z, z ′ ) .
∆ (z, Z) = min
′
z ∈Z

A
We also define, with a small abuse of notation, ℓA∆ (X , Z; f ) = ℓ∆ (f (X ), Z), where f (X ) returns
a labeling vector which consists of labels for each instance in the bag X . It is obvious that this loss
underestimates the true loss. Nevertheless, we can easily extend [8, Proposition 3.1 to 3.3] to thebag case, and prove that ℓA∆ /(1 − η) is an upper bound to ℓ∆ in expectation, where η is a factor
between 0 and 1, and its value depends on the hardness of the problem. Like the definition in [8], ηcorresponds to the maximum probability of an extra label co-occurring with the true label over alllabels and instances. Hence, minimizing the ambiguous loss we are actually minimizing an upperbound of the true loss. It is a known problem that direct minimization of this loss is hard, so in thefollowing we introduce another loss that upper bounds ℓA∆ which can be minimized efficiently.

We assume that the prediction function f (x) we are searching for is equal to arg maxy∈Y F (x, y).
In this framework we can interpret the value of F (x, y) as the confidence of the classifier in assigningx to the class y. We also assume the standard linear model used in supervised multiclass learning [9].
In particular the function F (x, y) is set to be w · φ(x) ⊗ ψ(y), where φ and ψ are the feature andlabel space mapping [20], and ⊗ is the Kronecker product1. We can now define F(X , y; w) =PM
m=1 F (xm , ym ), which intuitively is gathering from each instance in X the confidence on thelabels in y. With the definitions above, we can rewrite the function F as
F(X , y; w) =MX

F (xm , ym ) =

m=1

M
X

w · φ(xm ) ⊗ ψ(ym ) = w · Φ(X , y) ,

(2)

m=1

PM
where we defined Φ(X , y) = m=1 φ(xm ) ⊗ ψ(ym ). Hence the function F can be defined as thescalar product between w and a joint feature map between the bag X and the labeling vector y.
Remark. If the prior probabilities of every candidate labeling vectors zl ∈ Z are also available,
they could be incorporated by slightly modifying the feature mapping scheme in (2).
We can now introduce the following loss function
ℓmax (X , Z; w) = max ℓA∆ (z̄, Z) + F(X , z̄; w) − max F(X , z; w)
z̄ ∈Z
/

z∈Z

(3)
+

where |x|+ = max(0, x). The following proposition shows that ℓmax upper bounds ℓA∆.
1

For simplicity we will omit the bias term here, it can be easily added by modifying the feature mapping.

3

Proposition. ℓmax (X , Z; w) ≥ ℓA
∆ (X , Z; w) .
Proof. Define ẑ = arg maxz∈Y M F(X , z; w). If ẑ ∈ Z then ℓmax (X , Z; w) ≥ ℓA
∆ (X , Z; w) = 0.
We now consider the case in which ẑ ∈/ Z. We have thatAℓA
∆ (X , Z; w) ≤ ℓ∆ (ẑ, Z) + F(X , ẑ; w) − max F(X , z; w)
z∈Z

(z̄,
Z)
+
F(X
,
z̄;
w)
− max F(X , z; w) ≤ ℓmax (X , Z; w) .
≤ max ℓA
∆
z̄ ∈Z
/

z∈Z



The loss ℓmax is non-convex, due to the second max(·) function inside, but in Section 3 we will
introduce an algorithm to minimize it efficiently.
2.2 A probabilistic interpretation
It is possible to gain additional intuition on the proposed loss function ℓmax through a probabilistic
interpretation of the problem. It is helpful to look at the discriminative model for supervised learning
first, where the goal is to learn the model parameters θ for the function P (y|x; θ), from a predefined modeling class Θ. Instead of directly maximizing the log-likelihood for the training data, analternative way is to maximize the log-likelihood ratio between the correct label and the most likely
incorrect one [9]. On the other hand, in the CLS setting the correct labeling vector for X is unknown,
but it is known to be a member of the candidate set Z. Hence we could maximize the log-likelihood
ratio between P (Z|X ; θ) and the most likely incorrect labeling vector which is not member of Z
(denoted as z̄). However, the correlations between different vectors in Z are not known, so theinference could be arbitrarily hard. Instead, we could approximate the problem by considering justthe most likely correct member of Z. It can be easily verified that maxz∈Z P (z|X ; θ) is a lower
bound of P (Z|X ; θ). The learning problem becomes to minimize the ratio for the bag:
− log

P (Z|X ; θ)maxz∈Z P (z|X ; θ)
≈ − log.
maxz̄∈Z
P
(z̄|X
;
θ)
max
/
z̄ ∈Z
/ P (z̄|X ; θ)(4)

If we assume independence between the instances in the bag, (4) can be factorized as:QXX
maxz∈Z m P (zm |xm ; θ)Q= max
log P (zm |xm ; θ) .
log P (z̄m |xm ; θ) − max
− log
z∈Z
z̄ ∈Z
/
maxz̄∈Z/m P (z̄m |xm ; θ)mm

If we take the margin into account, and assume a linear model for the log-posterior-likelihood, we
obtain the loss function in (3).

3 MMS: The Maximum Margin Set Learning Algorithm
Using the square norm regularizer as in the SVM and the loss function in (3), we have the following
optimization problem for the CLS learning problem:
min
w

N
λ
1 X
ℓmax (Xi , Zi ; w)
kwk22 +
2
N i=1

(5)

This optimization problem (5) is non-convex due to the non-convex loss function (3). To convexify
this problem, one could approximate the second max(·) in (3) with the average over all the labelingvectors in Zi . Similar strategies have been used in several analogous problems [8, 24]. However, theapproximation could be very loose if the number of labeling vectors is large. Fortunately, although
the loss function is not convex, it can be decomposed into a convex and a concave part. Thus the
problem can be solved using the constrained concave-convex procedure (CCCP) [19, 23].
3.1 Optimization using the CCCP algorithm
The CCCP solves the optimization problem using an iterative minimization process. At each roundr, given an initial w(r) , the CCCP replaces the concave part of the objective function with its firstorder Taylor expansion at w(r) , and then sets w(r+1) to the solution of the relaxed optimization
problem. When this function is non-smooth, such as maxz∈Zi F(Xi , z; w) in our formulation, thegradient in the Taylor expansion must be replaced by the subgradient2. Thus, at the r-th round, the2
Given a function g, its subgradient ∂g(x) at x satisfies: ∀u, g(u) − g(x) ≥ ∂g(x) · (u − x). The set of
all subgradients of g at x is called the subdifferential of g at x.

4

CCCP replaces maxz∈Zi F(Xi , z; w) in the loss function by
max F(Xi , z; w(r) ) + (w − w(r) ) · ∂ max F(Xi , z; w) .
z∈Zi

(6)

z∈Zi

The subgradient of a point-wise maximum function g(x) = maxi gi (x) is the convex hull of theunion of subdifferentials of the subset of the functions gi (x) which equal g(x) [4]. Defining by(r)
Ci = {z ∈ Zi : F(Xi , z; w(r) ) = maxz′ ∈Zi F(Xi , z ′ ; w(r) )}, the subgradient of the function
P (r)
P (r)
P (r)
maxz∈Zi F(Xi , z; w) equals to l αi,l ∂F(Xi , zi,l ; w) = l αi,l Φ(Xi , zi,l ), with l αi,l = 1,
(r)

(r)

and αi,l ≥ 0 if zi,l ∈ Ci and αi,l = 0 otherwise. Hence we have



 X
X (r)
(r)
αi,l = max w(r) · Φ(Xi , z) .
αi,l w(r) · Φ(Xi , zi,l ) = max w(r) · Φ(Xi , z)
z∈Zi

l

z∈Zi

(r)

l:zi,l ∈Ci

(r)

(r)

(r)

We are free to choose the values of the αi,l in the convex hull, here we choose to set αi,l = 1/|Ci |(r)for ∀zi,l ∈ Ci . Using (6) the new loss function becomes(r)ℓcccp (Xi , Zi ; w) = maxz̄ ∈/ Zi ℓA∆ (z̄, Zi ) + w · Φ(Xi , z̄) − w ·

1
(r)
|Ci |

P

(r)

z∈Ci

Φ(Xi , z), (7)+Replacing the non-convex loss ℓmax in (5) with (7), the relaxed convex optimization program at r-th
round of the CCCP is
min
w

N
λ
1 X (r)ℓ(Xi , Zi ; w)
kwk22 +
2
N i=1 cccp

(8)

(r)

With our choice of αi,l , in the first round of the CCCP when w is initialized at 0, the second max(·)
in (3) is approximated by the average over all the labeling vectors. The CCCP algorithm is guaranteed to decrease the objective function and it converges to a local minimum solution of (5) [23].
3.2 Solve the convex optimization problem using the Pegasos framework
In order to solve the relaxed convex optimization problem (8) efficiently at each round of the CCCP,
we have designed a stochastic subgradient descent algorithm, using the Pegasos framework developed in [18]. At each step the algorithm takes K random samples from the training set and calculates
an estimate of the subgradient of the objective function using these samples. Then it performs a subgradient descent step with decreasing learning rate, followed by a projection of the solution into
the space where the optimal solution lives. An upper bound on the radius of the ball in which the
optimal hyperplane lives can be calculated by considering thatN
λ ∗ 2
1 X (r)λkw k2 ≤ min kwk22 +ℓ(Xi , Zi ; w) ≤ Bw
2
2
N i=1 cccp(r)where w∗ is the optimal solution of (8), and B = maxi (ℓcccp (Xi , Zi ; 0)). If we use ∆(zm , ym ) =1(zm 6=ym ) in (7), B equals the maximum number of instances in the bags. The details of the Pegasos
algorithm for solving (8) are given in Algorithm 2. Using the theorems in [18] it is easy to show thate 1/(λε)) iterations Algorithm 2 converges in expectation to a solution of accuracy ε.
after O

Efficient implementation. Note that even if we solve the problem in the primal, we can still use
nonlinear kernels without computing the nonlinear mapping φ(x) explicitly. Since the implementation method is similar to the one described in [18, Section 4] for lack of space we omit the details.
Greedily searching for the most violating labeling vector ẑk in line 4 of Algorithm 2 can be computational expensive. Dynamic programming can be carried out to reduce the computational cost
since the contribution of each instance is additive over different labels. Moreover, by looking into
the structure of Zi , the computational time can be further reduced. In the general situation, theQMiworst case complexity of searching the maximum of z̄ ∈/ Zi is O( m=1
Ci,m ), where Ci,m is thenumber of unique possible labels for xi,m in Zi (usually Ci,m ≪ Li ). This complexity can begreatly reduced when there are special structures such as graphs and trees in the labeling set. Seefor example [20, Section 4] for a discussion on some specific problems and special cases.
5

Algorithm 1 The CCCP algorithm for solving MMS
1: initialize: w(1) = 0
2: repeat(r)
3:
Set Ci = {z ∈ Zi : F(Xi , z; w(r) ) = maxz′ ∈Zi F(Xi , z ′ ; w(r) )}4:
Set w(r+1) as the solution of the convex optimization problem (8)5: until convergence to a local minimum
6: output:w(r+1)

Algorithm 2 Pegasos Algorithm for Solving Relaxed-MMS (8)(r)

1: Input: w0 , {Xi , Zi , Ci }N
i=1 , λ, T , K, B
2: for t = 1, 2, . . . , T do
3:
Draw at random At ⊆ {1, . . . , N }, with |At | = K
A4:Compute ẑk = arg maxz̄∈Z/ k ℓ∆ (z̄, Zk ) + wt · Φ(Xk , z̄)5:6:∀k ∈ At(r)+
Set At = {k ∈ At : ℓcccp (Xk , Zk ; wt ) >
0}
P

(r)
1 P
1
1
+
Set wt+ 2 = (1 − t )wt + λKt k∈A
|
−
Φ(X
,
ẑ
)
(r) Φ(Xk , z)/|Ci
k
k
z∈Ci
t

 p

wt+1 = min 1, 2B/λ/kwt+ 12 k wt+ 21
8: end for
9: Output: wT +1
7:

4 Experiments
In order to evaluate the proposed algorithm, we first perform experiments on several artificial
datasets created from standard machine learning databases. Finally, we test our algorithm on one of
the examples motivating our study — learning a face recognition system from news images weakly
annotated by their associated captions. We benchmark MMS against the following baselines:• SVM: we train a fully-supervised SVM classifier using the ground-truth labels by considering every instance separately while ignoring the other candidate labels. Its performancecan be considered as an upper bound for the performance using candidate labels. In all our
experiments, we use the LIBLINEAR [11] package and test two different multiple-classextensions, the 1-vs-All method using L1-loss (1vA-SVM) and the method by Crammer
and Singer [9] (MC-SVM).
• CL-SVM: the Candidate Labeling SVM (CL-SVM) is a naive approach which transforms
the ambiguous labeled data into a standard supervised representation by treating all possible labels of each instance as true labels. Then it learns 1-vs-All SVM classifiers from theresulting dataset, where the negative examples are instances which do not have the corresponding label in their candidate labeling set. A similar baseline has been used in binary
MIL literature [5].
• MIML: we also compared with two SVM-based MIML algorithms3: MIMLSVM [25] andM3 MIML [24]. We train the MIML algorithms by treating the labels in Zi as a label forthe bag. During the test phase, we consider each instance separately and predict the labels
as: y = arg maxy∈Y Fmiml (x, y), where Fmiml is the obtained classifier, and Fmiml (x, y)
can be interpreted as the confidence of the classifier in assigning the instance x to the classy. We would like to underline that although some of the experimental setups may favor ouralgorithm, we include the comparison between MMS and MIML algorithms because to thebest of our knowledge it is the only existing principle framework for modeling instance bagswith multiple labels. MIML algorithms may still have their own advantage in scenarios
when no prior knowledge is available about the instances within a bag.
3
We used the original implementation at http://lamda.nju.edu.cn/data.ashx#code. We did
not compare against MIMLBOOST [25], because it does not scale to all the experiments we conducted. Besides, MIMLSVM [25] does not scale to data with high dimensional feature vectors (e.g., news20 which has
a 62,061-dimensions features). Running the MATLAB implementation of M3 MIML [24] on problems withmore than a few thousand samples is computational infeasible. Thus, we will only report results using this twobaseline methods on small size problems, where they can be finished in a reasonable amount of time.

6

usps (B=5, N=1,459)
100

letter (B=8, N=1,875)
80
70Classification rate

news20 (B=5, N=3,187)
90
80

80

covtype (B=4, N=43,575)
80

60

60
70
60

50

40
60

40
40

20
10

25

50

L

100

200

20
10

20

50

30
50

100

200

400

40
10

50

L

100

200

L

400

0
10

25

50

100

200

L

Figure 1: (Best seen in colors) Classification performance of different algorithms on artificial datasets.
We implemented our MMS algorithm in MATLAB4 , and used a value of the 1/N for the regularization parameter λ in all our experiments. In (1) we used ∆(zm , ym ) = 1(zm 6= ym ). For a faircomparison, we used linear kernel for all the methods. The cost parameter for SVM algorithms is
selected from the range C ∈ {0.1, 1, 10, 100, 1000}. The bias term is used in all the algorithms.
4.1 Experiments on artificial data
We create several artificial datasets using four widely used multi-class datasets (usps, letter, news20
and covtype) from the LIBSVM [6] website. The artificial training sets are created as follows: wefirst set at random pairs of classes as “correlated classes”, and as “ambiguous classes”, where theambiguous classes can be different from the correlated classes. Following that, instances are grouped
randomly into bags of fixed size B with probability at least Pc that two instances from correlatedclasses will appear in the same bag. Then L ambiguous labeling vectors are created for each bag,by modifying a few elements of the correct labeling vector. The number of the modified element is
randomly chosen from {1, . . . , B}, and the new labels are chosen among a predefined ambiguous
set. The ambiguous set is composed by the other correct labels from the same bag (except the trueone) and a subset of the ambiguous pairs of all the correct labels from the bag. The probability ofwhether the ambiguous pair of a label is present equals Pa . For testing, we use the original test set,and each instance is considered separately.
Varying Pc , Pa , and L we generate different dataset difficulty levels to evaluate the behaviour of
the algorithms. For example, when Pa > 0, noisy labels are likely to be present in the labelingset. Meanwhile, Pc controls the ambiguity within the same bags. If Pc is large, instances fromtwo correlated classes are likely to be grouped into the same bag, thus it becomes more difficult todistinguish between these two classes. The parameters Pc and Pa are chosen from {0, 0.25, 0.5}.
For each difficulty level, we run three different training/test splits.
In figure 1, we plot the average classification accuracy. Several observations can be made: first,
MMS achieves results close to the supervised SVM methods, and better than all other baselines.
As MMS uses a similar multi-class loss as MC-SVM, it even outperforms 1vA-SVM when theloss has its advantage (e.g., on the ‘letter’ dataset). For the ‘covtype’ dataset, the performancegap between MMS and SVM is more visible. It may because ‘covtype’ has a class unbalance,
where the two largest classes (among seven) dominate the whole dataset (more than 85% of thetotal number of samples). Second, the change on performance of MMS is small when the size of thecandidate labeling set grows. Moreover, when correlated instances and extra noisy labels are present
in the dataset, the baseline methods’ performance drops by several percentages, while MMS is lessaffected. The CCCP algorithm usually converges in 3 – 5 rounds, and the final performance is about
5% – 40% higher compared to the results obtained after the first round, especially when L is large.
This behavior also proves that approximating the second max(·) function in the loss function (3)with the average over all the possible labeling vectors can lead to poor performance.
4.2 Applications to learning from images & captions
A huge amount of images with accompanying text captions are available on the web. This cheap
source of information has been used, e.g., to name faces in images using captions [3, 13]. Thanks
to the recent developments in the computer vision and natural language processing fields, faces in
the images can be detected by a face detector and names in the captions can be identified using alanguage parser. The gathered data can then be used to train visual classifiers, without human’s
4

Code available at http://dogma.sourceforge.net/

7

President Barack Obama and first lady
Michelle Obama wave from the steps of
Air Force One as they arrive in Prague,
Czech Republic.

Z:

»

z1

z2

z3 z4

z5

z6

na
nb

na
◦

◦
nb

◦
na

nb
◦

nb
na

–

← facea← faceb

Figure 2: (Left): An example image and its associated caption. There are two detected faces facea and faceb
and two names Barack Obama (na ) and Michelle Obama (nb ) from the caption. (Right): The candidate labelingset for this image-captions pairs. The labeling vectors are generated using the following constrains: i). a facein the image can either be assigned with a name from its caption, or it possibly corresponds to none of them (aNULL class, denoted as ◦); ii) a face can be assigned to at most one name; iii) a name can be assigned to at mosta face. Differently from previous methods, we do not allow the labeling vector with all the faces assigned to
the NULL class, because it would lead to the trivial solution with 0 loss by classifying every instance as NULL.

Table 1: Overall face recognition accuracy
DatasetYahoo!

1vA-SVM
81.6% ± 0.6

MC-SVM
87.2% ± 0.3

CL-SVM
76.9% ± 0.2

MIMLSVM
74.7% ± 0.9

MMS85.7% ± 0.5

effort in labeling the data. This task is difficult due to the so called “correspondence ambiguity”
problem: there could be more than one face and name appearing in the image-caption pairs, and not
all the names in the caption appear in the image, and vice versa. Nevertheless, this problem can benaturally formulated as a CLS problem. Since the names of the key persons in the image typicallyappear in the captions, combined with other common assumptions [3, 13], we can easily generate
the candidate labeling sets (see Figure 2 for a practical example).
We conducted experiments on the Labeled Yahoo! News dataset5 [3, 13]. The dataset is fully annotated for association of faces in the image with names in the caption, precomputed facial features
were also available with the dataset. After preprocessing, the dataset contains 20071 images and31147 faces. There are more than 10000 different names from the captions. We retain the 214 mostfrequent ones which occur at least 20 times, and treat the other names as NULL. The experiments
are performed over 5 different permutations, sampling 80% images and captions as training set, andusing the rest for testing. During splitting we also maintain the ratio between the number of samples
from each class in the training and test set. For all algorithms, NULL names are considered as anadditional class, except for MIML algorithms where unknown faces can be automatically considered as negative instances. The performance of the algorithms is measured by how many faces inthe test set are correctly labeled with their name. Table 1 summarizes the results. Similar observations can also be made here: MMS achieves performance comparable to the fully-supervised SVM
algorithms (4.1% higher than 1vA-SVM on Yahoo! data), while outperforming the other baselines
for ambiguously labeled data.

5 Conclusion
In this paper, we introduce the “Candidate Labeling Set” problem where training samples containmultiple instances and a set of possible labeling vectors. We also propose a large margin formulationof the learning problem and an efficient algorithm for solving it. Although there are other similar
frameworks, such as MIML, which also investigate learning from instance bags with multiple labels,
our framework is different since it makes an explicit effort to label and to consider each instance inthe bag during the learning process, and allows noisy labels in the training data. In particular,
our framework provides a principled way to encode prior knowledge about relationships between
instances and labels, and these constraints are explicitly taken into account into the loss function
by the algorithm. The use of this framework does not have to be limited to data which is naturallygrouped in multi-instance bags. It could be also possible to group separate instances into bags andsolve the learning problem using MMS, when there are labeling constraints between these instances(e.g., a clustering problem with linkage constraints).
Acknowledgments We thank the anonymous reviewers for their helpful comments. The Labeled Yahoo!
News dataset were kindly provided by Matthieu Guillaumin and Jakob Verbeek. LJ was sponsored by the EU
project DIRAC IST-027787 and FO was sponsored by the PASCAL2 NoE under EC grant no. 216886. LJ also
acknowledges PASCAL2 Internal Visiting Programme for supporting traveling expense.
5

Dataset available at http://lear.inrialpes.fr/data/

8

References[1] S. Andrews, I. Tsochantaridis, and T. Hofmann. Support vector machines for multiple-instancelearning. In Proc. NIPS, 2003.
[2] K. Barnard, P. Duygulu, D. Forsyth, N. de Freitas, D. Blei, and M. Jordan. Matching words
and pictures. JMLR, 3:1107–1135, 2003.
[3] T. Berg, A. Berg, J. Edwards, and D. Forsyth. Who’s in the picture? In Proc. NIPS, 2004.
[4] D. P. Bertsekas. Convex Analysis and Optimization. Athena Scientific, 2003.
[5] R. C. Bunescu and R. J. Mooney. Multiple instance learning for sparse positive bags. In Proc.
ICML, 2007.
[6] C. C. Chang and C. J. Lin. LIBSVM: A Library for Support Vector Machines, 2001. Software
available at http://www.csie.ntu.edu.tw/˜cjlin/libsvm.
[7] O. Chapelle, A. Zien, and B. Schölkopf (Eds.). Semi-supervised Learning. MIT Press, 2006.
[8] T. Cour, B. Sapp, C. Jordan, and B. Taskar. Learning from ambiguously labeled images. In
Proc. CVPR, 2009.
[9] K. Crammer and Y. Singer. On the algorithmic implementation of multiclass kernel-based
vector machines. JMLR, 2:265–292, 2001.
[10] T. G. Dietterich, R. H. Lathrop, T. Lozano-Perez, and A. Pharmaceutical. Solving the multipleinstance problem with axis-parallel rectangles. Artificial Intelligence, 39:31–71, 1997.
[11] R.-E. Fan, K.-W. Chang, C.-J. Lin, S. S. Keerthi, and S. Sundarajan. LIBLINEAR: A library
for large linear classification. JMLR, 9:1871–1874, 2008.
[12] Y. Grandvalet. Logistic regression for partial labels. In Proc. IPMU, 2002.
[13] M. Guillaumin, J. Verbeek, and C. Schmid. Multiple instance metric learning from automatically labeled bags of faces. In Proc. ECCV, 2010.
[14] A. Gupta and L. Davis. Beyond nouns: Exploiting prepositions and comparative adjectives forlearning visual classifiers. In Proc. ECCV, 2008.
[15] E. Hüllermeier and J. Beringe. Learning from ambiguously labelled example. Intelligent Data
Analysis, 10:419–439, 2006.
[16] L. Jie, B. Caputo, and V. Ferrari. Who’s doing what: Joint modeling of names and verbs for
simultaneous face and pose annotation. In Proc. NIPS, 2009.
[17] R. Jin and Z. Ghahramani. Learning with multiple labels. In Proc. NIPS, 2002.
[18] S. Shalev-Shwartz, Y. Singer, and N. Srebro. Pegasos: Primal Estimated sub-GrAdient SOlverfor SVM. In Proc. ICML, 2007.
[19] A. J. Smola, S. V. N. Vishwanathan, and T. Hofmann. Kernel methods for missing variables.
In Proc. AISTAT, 2005.
[20] I. Tsochantaridis, T. Joachims, T. Hofmann, and Y. Altun. Large margin methods for structured
and interdependent output variables. JMLR, 6:1453–1484, 2005.
[21] E.P Xing, A.Y. Ng, M.I. Jordan, and S. Russell. Distance metric learning with application toclustering with side-information. In Proc. NIPS, 2002.
[22] C.-N. Yu and T. Joachims. Learning structural svms with latent variables. In Proc. ICML,
2009.
[23] A. Yuille and A. Rangarajan. The concave-convex procedure. Neural Computation, 15:915–
936, 2003.
[24] M.-L. Zhang and Z.-H. Zhou. M3 MIML: A maximum margin method for multi-instance multilabel learning. In Proc. ICDM, 2008.
[25] Z.-H. Zhou and M.-L. Zhang. Multi-instance multi-label learning with application to scene
classification. In Proc. NIPS, 2006.
[26] X. Zhu. Semi-supervised learning literature survey. Technical Report 1530, Computer Sciences, University of Wisconsin-Madison, 2005.

9