Thibaut Durand
email: thibaut.durand@lip6.fr

Nicolas Thome
email: nicolas.thome@lip6.fr

Matthieu Cord
email: matthieu.cord@lip6.fr

MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking

In this work, we propose a novel Weakly Supervised Learning (WSL) framework dedicated to learn discriminative part detectors from images annotated with a global label. Our WSL method encompasses three main contributions. Firstly, we introduce a new structured output latent variable model, Minimum mAximum lateNt sTRucturAl SVM (MANTRA), which prediction relies on a pair of latent variables: h + (resp. h -) provides positive (resp. negative) evidence for a given output y. Secondly, we instantiate MANTRA for two different visual recognition tasks: multiclass classification and ranking. For ranking, we propose efficient solutions to exactly solve the inference and the lossaugmented problems. Finally, extensive experiments highlight the relevance of the proposed method: MANTRA outperforms state-of-the art results on five different datasets.

Introduction

Deep learning with Convolutional Neural Networks (CNN) [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] are becoming a key ingredient of visual recognition systems. Internal CNN representations trained on large scale datasets [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] currently provide state-of-the-art features for various tasks, e.g., image classification or object detection [START_REF] Oquab | Learning and transferring mid-level image representations using convolutional neural networks[END_REF][START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF]. To overcome the limited invariance capacity of CNN, bounding box annotations are often used.

However, collecting full annotations for all images in a large dataset is an expensive task: whereas several millions of images annotated with a global label are nowadays available, while only thousands of accurate bounding box annotations exist [START_REF] Blaschko | Tutorial: Visual learning with weak supervision[END_REF]. This observation makes the development of Weakly Supervised Learning (WSL) models appealing.

Regarding WSL models, one of the most famous approach is the Deformable Part Model (DPM) [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF], or its extension to structured output prediction, Latent Structural SVM (LSSVM) [START_REF] Yu | Learning structural svms with latent variables[END_REF]. Recently, several attempts have been devoted to applying the LSSVM framework for object or scene recognition problems [START_REF] Kumar | Self-paced learning for latent variable models[END_REF][START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF][START_REF] Russakovsky | Objectcentric spatial pooling for image classification[END_REF][START_REF] Parizi | Reconfigurable models for scene recognition[END_REF][START_REF] Bilen | Object classification with latent window parameters[END_REF][START_REF] Sun | Learning discriminative part detectors for image classification and cosegmentation[END_REF][START_REF] Sharma | Discriminative spatial saliency for image classification[END_REF][START_REF] Durand | Incremental learning of latent structural svm for weakly supervised image classification[END_REF]]. In this paper, we tackle the WSL problem of learning part detectors from images annotated with a global label. To this end, we introduce a novel structured output latent variable framework, MANTRA (Minimum mAximum la-teNt sTRucturAl SVM), which incorporates a pair of latent variables (h + , h -), and sum their prediction scores.

To illustrate the rationale of the approach, let us consider a multi-class classification instantiation of MANTRA, where latent variables h correspond to part localizations. h + is the max scoring latent value for each class y, i.e. the region which best represents class y. h -is the min scoring latent value, and can thus be regarded as an indicator of the absence of class y in the image.

To highlight the importance of the pair (h + , h -), we show in Figure 1, for an image of the class library, classification scores for each latent location using (on the left) the library classifier s l (the correct one) and (on the right) the cloister classifier s c (a wrong one). h + (resp. h -) regions are boxed in red (resp. blue). As we can see, the prediction score s l (h + ) = 1.8 for the correct library classifier is large, since the model finds strong local evidence h + of its presence (bookcase), and no clear evidence of its absence (medium score s l (h -) = 0.1). Contrarily, the prediction score for the cloister classifier s c is substan-tially smaller: although the model heavily fires on the vault (s c (h + ) = 1.5), it also finds clear evidence of the absence of cloister, here books (s c (h -) = -0.8). As a consequence, MANTRA correctly predicts the class library 1 .

From the intuition given in Figure 1, we provide in Section 3 a formal definition of MANTRA, and propose a generic and efficient optimization scheme to train it. In addition, we propose two instantiations of our model: multiclass classification (Section 4.1) and ranking, for which specific solutions must be designed to handle the large output space (Section 4.2). In the experiments (Section 5), we show that MANTRA trained upon deep features outperforms state-of-the-art performances on five different datasets. We now detail state-of-the-art methods which are the most connected to ours.

Related Works & Contributions

The computer vision community is currently witnessing a revolutionary change, essentially caused by Convolutional Neural Networks (CNN) and deep learning. CNN reached an outstanding success in the context of large scale image classification (ImageNet) [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], significantly outperforming handcrafted features based on Bag of Words (BoW) models [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF][START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF][START_REF] Avila | Pooling in image representation: the visual codeword point of view[END_REF][START_REF] Goh | Learning Deep Hierarchical Visual Feature Coding[END_REF], or biologically-inspired networks [START_REF] Serre | Robust object recognition with cortex-like mechanisms[END_REF][START_REF] Thériault | Extended Coding and Pooling in the HMAX Model[END_REF][START_REF] Thériault | Dynamic scene classification: Learning motion descriptors with slow features analysis[END_REF]. Deep features also prove their efficiency for transfer learning: state-of-the-art performances on standard benchmarks (PASCAL VOC, 15-Scenes, MIT67, etc) are nowadays obtained with deep features as input. Recent studies reveal that performances can further be improved by collecting large datasets that are semantically closer to the target domain [START_REF] Zhou | Learning Deep Features for Scene Recognition using Places Database[END_REF], or by fine-tuning the network with data augmentation [START_REF] Chatfield | Return of the devil in the details: Delving deep into convolutional nets[END_REF].

Despite their excellent performances, current CNN architectures only carry limited invariance properties. Recently, attempts have been made to overcome this limitation. Some methods revisit the BoW model with deep features as local region activations [START_REF] He | Spatial pyramid pooling in deep convolutional networks for visual recognition[END_REF][START_REF] Gong | Multi-scale orderless pooling of deep convolutional activation features[END_REF]. The drawback is that background regions are encoded into the final representation, decreasing its discriminative power. In [START_REF] Zhang | PANDA: Pose Aligned Networks for Deep Attribute Modeling[END_REF], it is shown that aligning parts with poselet detectors makes human attribute recognition with deep features much more efficient. Although we share with [START_REF] Zhang | PANDA: Pose Aligned Networks for Deep Attribute Modeling[END_REF] the motivation for part alignment, [START_REF] Zhang | PANDA: Pose Aligned Networks for Deep Attribute Modeling[END_REF] focuses on specific pre-trained poselet detectors, which do not generalize to other tasks. In this paper, we tackle the problem of learning part detectors that are optimal for the task, in a weakly supervised manner.

The DPM model [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] is extremely popular for WSL, due to its excellent performances for weakly supervised object detection. Several attempts have been devoted to using DPM and its generalization to structured output prediction, 1 Many additional visualizations highlighting the relevance of training MANTRA with (h + , h -) are shown in Supplementary, Figures 2,3,4.

LSSVM [START_REF] Yu | Learning structural svms with latent variables[END_REF], for weakly supervised scene recognition and object localization. Some approaches learn single part detectors [START_REF] Kumar | Self-paced learning for latent variable models[END_REF][START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF][START_REF] Russakovsky | Objectcentric spatial pooling for image classification[END_REF][START_REF] Bilen | Object classification with latent window parameters[END_REF], whereas other methods enrich the model with multiple parts [START_REF] Sadeghi | Latent pyramidal regions for recognizing scenes[END_REF][START_REF] Parizi | Reconfigurable models for scene recognition[END_REF], optionally incorporating priors, e.g. sparsity or diversity, in order to learn sensible models [START_REF] Juneja | Blocks that shout: Distinctive parts for scene classification[END_REF][START_REF] Sun | Learning discriminative part detectors for image classification and cosegmentation[END_REF]. Due to the non-convexity of LSSVM objective, other approaches attempt to improve LSSVM training. In [START_REF] Kumar | Self-paced learning for latent variable models[END_REF][START_REF] Russakovsky | Objectcentric spatial pooling for image classification[END_REF][START_REF] Bilen | Object classification with latent window parameters[END_REF], different solutions are explored to apply the curriculum learning idea, i.e. how to find easy samples to incrementally solve the non-convex optimization problem and reach better local optima. However, it should be noted that all these methods still use the LSSVM prediction rule. We follow a different route with MANTRA, by proposing a new prediction function which combines a max and min scoring.

In this paper, we also tackle the important problem of learning to rank, since many computer vision tasks are evaluated with ranking metrics, e.g. Average Precision (AP) in PASCAL VOC. Optimizing ranking models with AP is challenging. In the fully supervised case, an elegant instantiation of structural SVM is introduced in [START_REF] Yue | A support vector method for optimizing average precision[END_REF], making it possible to optimize a convex upper bound over AP. On the contrary, few works tackle the problem of weakly supervised ranking from the latent structured output perspective, with the exception of [START_REF] Behl | Optimizing average precision using weakly supervised data[END_REF]. In [START_REF] Behl | Optimizing average precision using weakly supervised data[END_REF], the authors introduce LAPSVM, and point out that directly using LSSVM [START_REF] Yu | Learning structural svms with latent variables[END_REF] for this purpose is not practical, mainly because no algorithm for solving the loss-augmented inference problem exists. LAPSVM introduces a tractable optimization by defining an ad-hoc prediction rule dedicated to ranking: first the latent variables are fixed, and then an optimal ranking with fixed latent variables is found. Our WSL method is applicable to any structured output space, and we show its relevance for weakly supervised AP ranking.

This paper presents a weakly supervised learning scheme, which encompasses the following contributions:

• We introduce a new latent structured output learning framework, MANTRA, which prediction function is based on a pair of latent variables (h + , h -). In addition, we propose a direct cutting plane optimization procedure for training the model, which is efficient.

• We propose two instantiations of MANTRA: multiclass classification and ranking. We show that both inference and loss-augmented inference problems can be solved exactly and efficiently in the ranking case.

• We report excellent results in different visual recognition tasks: MANTRA outperforms state-of-the-art performances on five challenging visual datasets. In particular, we highlight that the model is able to detect parts witnessing the absence of a class, and show that the proposed ranking instantiation is able to further improve performances by a large margin.

Proposed Weakly Supervised Model

We present here the proposed WSL model: Minimum mAximum lateNt sTRucturAl SVM (MANTRA). Notations We first give some basic notations used in the (latent) structured output learning framework. We consider an input space X , that can be arbitrary, and a structured output space Y. For (x, y) ∈ (X × Y), we are interested in the problem of learning a discriminant function of the form: f : X → Y. In order to incorporate hidden parameters that are not available at training time, we augment the description between an input/output pair with a latent variable h ∈ H. We assume that a joint feature map Ψ(x, y, h) ∈ R d , describing the relation between input x, output y, and latent variable h, is designed. Our goal is to learn a prediction function f w , parametrized by w ∈ R d , so that the predicted output ŷ depends on w, Ψ(x, y, h) ∈ R. During training, we assume that we are given a set of N training pairs

(x i , y i ) ∈ (X × Y), i ∈ {1; N }.
Our goal is to optimize w in order to minimize a user-supplied loss function ∆(y i , ŷ) over the training set.

MANTRA Model

As mentioned in the introduction, the main intuition of the proposed MANTRA model is to equip each possible output y ∈ Y with a pair of latent variables

(h + i,y , h - i,y ). h + i,y (resp. h - i,y
) corresponds to the max (resp. min) scoring latent value, for input x i and output y:

h + i,y =arg max h∈H w, Ψ(x i , y, h) h - i,y =arg min h∈H w, Ψ(x i , y, h)
For an input/output pair (x i , y), the scoring of the model, D w (x i , y), sums h + i,y and h - i,y scores, as follows:

D w (x i , y) = w, Ψ(x i , y, h + i,y ) + w,Ψ(x i , y, h - i,y ) (1
) Finally, MANTRA prediction outputs ŷ = f w (x i ) which maximizes D w (x i , y) with respect to y:

ŷ = f w (x i ) = arg max y∈Y D w (x i , y) (2)

Learning Formulation

During training, we enforce the following constraints:

∀y = y i , D w (x i , y i ) ≥ ∆(y i , y) + D w (x i , y) (3)
Each constraint in Eq. ( 3) requires the scoring value D w (x i , y i ) for the correct output y i to be larger than the scoring value D w (x i , y) for each incorrect output y = y i , plus a margin of ∆(y i , y). ∆(y i , y), a user-specified loss, makes it possible to incorporate domain knowledge into the penalization. To give some insights of how the model parameters can be adjusted to fulfill constraints in Eq. ( 3), let us notice that:

• D w (x i , y i ), i.e.
the score for the correct output y i , can be increased if we find statistically high scoring variables h + i,yi , which represent strong evidence for the presence of y i , while enforcing h - i,yi variables not having large negative scores.

• D w (x i , y), i.e. the score for an incorrect output y, can be decreased if we find low scoring variables h + i,y , limiting evidence of the presence of y, while seeking h - i,y variables with large negatives scores, supporting the absence of output y.

To allow some constraints in Eq. ( 3) to be violated, we introduce the following loss function:

w (x i , y i ) = max y∈Y [∆(y i ,y)+D w (x i , y)-D w (x i , y i )] (4)
We show in supplementary material A.1 that w (x i , y i ) in Eq. ( 4) is an upper bound of ∆(ŷ, y i ).

Using the standard max margin regularization term w 2 , our primal objective function is defined as follows:

P(w) = 1 2 w 2 + C N N i=1 w (x i , y i ) (5)

Optimization

The problem in Eq. ( 5) is not convex with respect to w. To solve it, we propose an efficient optimization scheme based on a cutting plane algorithm with the one-slack formulation [START_REF] Joachims | Cutting-plane training of structural svms[END_REF]. Our objective function in Eq. ( 5) can thus be rewritten as follows:

min w,ξ 1 2 w 2 + Cξ s.t. ∀(ŷ 1 , . . . , ŷN ) ∈ Y N (6) 1 N N i=1 ∆(y i , ŷi ) + D w (x i , ŷi ) -D w (x i , y i ) ≤ ξ
The key idea of the 1-slack formulation in Eq. ( 6) is to replace the N slack variables (weak constraints) by a single shared slack variable ξ (strong constraint). It is shown in [START_REF] Joachims | Cutting-plane training of structural svms[END_REF] that this formulation helps speeding up the training of structural SVMs, reducing the complexity from being super-linear to linear in the number of training examples.

Cutting Plane Algorithm Based on the 1-slack formulation, we use a cutting plane strategy to optimize Eq. ( 6). Compared to sub-gradient methods, the cutting plane approach takes an optimal step in the current cutting plane model, leading to faster convergence [START_REF] Tsochantaridis | Large margin methods for structured and interdependent output variables[END_REF].

For convex optimization problems, the idea of the cutting plane method is to build an accurate approximation, underestimating the objective function. However, it cannot be directly applied for solving non-convex optimization problems, because the cutting plane approximation might not be underestimating the objective at all points, with the risk of missing good local minima [START_REF] Do | Regularized bundle methods for convex and non-convex risks[END_REF]. Based on [START_REF] Do | Regularized bundle methods for convex and non-convex risks[END_REF], we derive a non-convex cutting plane algorithm to solve Eq. ( 6). In particular, we use a method to detect and solve conflicts when adding a new cutting plane, as in [START_REF] Do | Regularized bundle methods for convex and non-convex risks[END_REF], in order to avoid overestimating the objective function. It is important to stress that the proposed approach consists in a direct optimization, contrarily to iterative methods, which usually solve a set of approximate problems, e.g. CCCP [START_REF] Yuille | The concave-convex procedure[END_REF].

The overall training scheme of MANTRA is shown in Algorithm 1. Starting from an initial cutting plane (Line 1), each cutting plane iteration consists in solving the resulting Quadratic Problem (QP) problem with the working set of cutting planes H (Line 5). As in [START_REF] Joachims | Cutting-plane training of structural svms[END_REF], we solve the QP in the dual, because |H| is generally much smaller than the input dimension. The dual formulation of Eq. ( 6) (Line 5) is derived in supplementary material A.2.1. Then, the current w solution (Line 7) is used to find the most violated constraint ŷ for each example (Line 10). The ŷ's are used to compute g (t) from the subgradient ∇ w w (Line 13), which computation is given in supplementary material A.2.2. g (t) serves to update the working set H at the next iteration. Finally, when adding a new cutting plane, we detect and solve conflicts (Line 15) using the method detailed in [START_REF] Do | Regularized bundle methods for convex and non-convex risks[END_REF]. The algorithm stops as soon as no constraint can be found that is violated by more than the desired precision ε (Line 16). 1: Initialize t ← 1, {ŷ i , h + i,ŷi , h - i,ŷi } i=1,...,N and compute initial cutting plane (g (1) , c (1) H ← (H ij ) 1≤i,j≤t where H ij = g (i) , g (j) 5:

α ← arg max α≥0 α T c -1 2 α T Hα s.t. α T 1 ≤ C 6: ξ ← 1 C (α T c -α T Hα) 7: w ← t i=1 α i g (i)
8:

t ← t + 1 9:
for i=1 to N do // Compute new cutting plane and solve conflict 13:

g (t) ← 1 N N i=1 -∇ w w (x i , y i ) 14: c (t) ← 1 N N i=1 ∆(y i , ŷi ) 15:
(g (t) , c (t) ) ← SolveConf lict(w, g (t) , c (t) ) 16: until w, g (t) ≥ c (t) -ξ -ε Output: w

MANTRA Instantiation

MANTRA instantiation consists in specifying a particular joint feature Ψ and loss function ∆. For each instantiation, training the model requires solving two problems: inference (Eq. ( 2)), and loss-augmented inference (Eq. ( 7)):

ŷ = arg max y∈Y ∆(y i , y) + D w (x i , y) (7)
In this section, we instantiate MANTRA for two WSL detection tasks: multi-class classification and ranking.

Multi-class Instantiation

For multi-class classification, the input x is an image, and the latent variable h is the location of a region (bounding box) in the image. The output space is the set of classes Y = {1, . . . , K}, where K is the number of classes. We use the standard joint feature map Ψ(x, y, h) = {I(y = 1)Φ(x, h), . . . , I(y = K)Φ(x, h)}, where Φ(x, h) ∈ R d is a vectorial representation of image x at location h, and

I(y = k) = 1 if y = k and I(y = k) = 0 if y = k. Ψ(x, y, h) is then a (K × d)-dimensional vector.
The loss function ∆ is the 0/1 loss. The inference and the lossaugmented inference are exhaustively solved.

Ranking Instantiation

Notations Following [START_REF] Yue | A support vector method for optimizing average precision[END_REF], our input for ranking is a set of N images x i : x = {x i , i = 1, . . . , N }. During training, each image is given its class information: x i ∈ P if it is labeled as positive, x i ∈ N otherwise. The structured output is a ranking matrix y of size N × N providing an ordering of the training examples, such that (a)

y ij = 1 if x i ≺ y x j 2 ; (b) y ij = -1 if x j ≺ y x i ; (c) y ij = 0 if x i
and x j are assigned the same rank. y * is the ground-truth ranking matrix, i.e. y * ij = 1 for (x i , x j ) ∈ P × N , y * ii = 0 and y * jj = 0 for (x i , x i ) ∈ P × P and (x j , x j ) ∈ N × N .

Joint Feature Map Ψ(x, y, h) is defined as follows:

Ψ(x,y,h) = 1 |P||N | xi∈P xj ∈N y ij [Φ(x i , h i,j )-Φ(x j , h j,i )] (8)
The latent space H corresponds to the set of latent variables for each pair of positive-negative examples: h = {(h i,j , h j,i ) ∈ H i × H j , (x i , x j ) ∈ P × N }, where H i (resp. H j ) is the set of locations in image x i (resp. x j ). Φ(x i , h i,j ) ∈ R d is thus a vectorial representation of image x i at location h i,j . Note that Ψ(x, y, h) in Eq. ( 8) is a generalization of the feature map used in [START_REF] Behl | Optimizing average precision using weakly supervised data[END_REF], where the selection of bounding boxes is specific to each image pair.

Loss Function During training, the goal is to minimize a given ranking loss function. In this paper, we especially focus on AP, with ∆ ap (y * , y) = 1 -AP (y * , y). As mentioned in Section 2, optimizing over ∆ ap is difficult, because ∆ ap does not decompose linearly in the examples [START_REF] Yue | A support vector method for optimizing average precision[END_REF]. In the WSL setting, the problem is exacerbated: for example, no efficient algorithm currently exists for solving the loss-augmented inference problem in the LSSVM case [START_REF] Yu | Learning structural svms with latent variables[END_REF], as pointed out in [START_REF] Behl | Optimizing average precision using weakly supervised data[END_REF].

We show here that inference and loss-augmented inference can be solved exactly and efficiently with MANTRA. Firstly, we show (Lemma 1) that in our ranking instantiation, D w in Eq. ( 1) can be computed a standard fully supervised feature map. This result has major consequences, which enables to decouple the optimization over y and h. Lemma 1. ∀(x, y), D w (x, y) in Eq. ( 1), for the ranking instantiation of Ψ given in Eq. ( 8), rewrites as A(x, y):

A(x, y) = 1 |P||N | xi∈P xj ∈N y ij ( w, Φ + -(x i ) -w, Φ + -(x j ) w, Φ + -(x i ) = max h∈Hi w, Φ(x i , h) + min h∈Hi w, Φ(x i , h)
The proof of Lemma 1 is given in supplementary B.1, and comes from an elegant symmetrization of the problem due to the max + min operation. The supervised feature map Φ + -(x i ) is the solution of the optimization over h, whatever y value.

We now explain how inference and loss-augmented inference can be efficiently solved with MANTRA. Proposition 1. Inference for the MANTRA ranking instantiation is solved exactly by sorting the examples in descending order of score s(i) = w, Φ + -(x i ) Proof. Since the inference consists in solving max y A(x, y), this is a direct consequence of Lemma 1: the problem reduces to solving a fully supervised ranking inference problem, where each example x i is represented by Φ + -(x i ). This is solved by sorting the example in descending order of score s(i) = w, Φ + -(x i ) [START_REF] Yue | A support vector method for optimizing average precision[END_REF]. Proposition 2. Loss-augmented inference for MANTRA (Eq. ( 7)), with the instantiation of Eq. ( 8), is equivalent to:

ŷ = arg max y∈Y [∆(y * , y) + A(x, y)] (9)
Proposition 2 directly follows from Lemma 1. This is a key result, since it allows to use MANTRA with different loss functions, as soon as there is an algorithm to solve the loss-augmented inference in the fully supervised setting. To solve it with ∆ ap , we use the greedy algorithm proposed by [START_REF] Yue | A support vector method for optimizing average precision[END_REF], which finds a globally optimal solution (see complexity analysis in supplementary B.2). Note that it is possible to use faster methods [START_REF] Mohapatra | Efficient optimization for average precision svm[END_REF] to address large-scale problem if required.

Experiments

In this section, we present an evaluation and analysis of MANTRA for multi-class classification and ranking tasks. In our implementation, we use MOSEK 3 to solve the Quadratic Problem (QP) at each cutting plane iteration (Line 5 of Algorithm 1 for MANTRA). The regularization parameter C is fixed to a large value, e.g. 10 54 .

Multi-class Classification

In this section, we analyze our multi-class model (section 4.1) for different bounding box scales (from 30% to 90% of the image size, with a step of 10%).

Datasets We evaluate our multi-class model for 4 different visual recognition tasks: scene categorization [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] (15-Scene dataset), cluttered indoor scenes [START_REF] Quattoni | Recognizing indoor scenes[END_REF] (MIT 67 Indoor Scenes), fine-grained recognition [START_REF] Yao | Grouplet: A structured image representation for recognizing human and object interactions[END_REF] (People Playing Musical Instrument, PPMI) and complex event and activity images [START_REF] Li | What, where and who? classifying events by scene and object recognition[END_REF] (UIUC-Sports dataset). Performances are evaluated with multi-class accuracy and follow the standard protocol for all databases (more details in supplementary C.1).

Features Each image region is described using deep features computed with Caffe CNN library [START_REF] Jia | Caffe: Convolutional architecture for fast feature embedding[END_REF]. We use the output of the sixth layer (after the rectified linear unit transformation (ReLU)), so that each region is represented by a 4096-dimensional vector. For UIUC-Sports and PPMI (resp. 15 Scene and MIT67), we use deep features based on a model pre-trained on ImageNet (resp. Places [START_REF] Zhou | Learning Deep Features for Scene Recognition using Places Database[END_REF]).

MANTRA Results

Firstly, we report MANTRA results with respect to the scale in Figure 2. It is worth pointing out that parts learned with a single region by MANTRA are able to improve performances over deep features computed on the whole image (s = 100%), e.g. 5 pt for PPMI. It confirms that using regions allows to find more discriminant representations. We observe that the performances on small scales remain very good: for example, results for scale s = 40% are as good as for s = 100% in PPMI and UIUC; although performances slightly decrease for 15-Scene and MIT67, they remain very competitive (see Table 1).

The previous results suggest the idea of combining several scales, which are expected to convey complementary informations. To perform scale combination, we use an Object-Bank (OB) [START_REF] Li-Jia Li | Object bank: A high-level image representation for scene classification & semantic feature sparsification[END_REF] strategy, which is often used in WSL works [START_REF] Sadeghi | Latent pyramidal regions for recognizing scenes[END_REF][START_REF] Juneja | Blocks that shout: Distinctive parts for scene classification[END_REF][START_REF] Sun | Learning discriminative part detectors for image classification and cosegmentation[END_REF]. Our OB is simple, using maxpooling over P parts models and K classes, without SPM. Our final representation is thus compact (P × K). Ultimately, we use a linear SVM classifier for classification. Results for our multi-scale method are shown in Table 1: we can notice that performances improve compared to the best mono-scale results (4 pt for MIT67, 7 pt for PPMI), validating the fact that taking into account different scales enable catching complementary and discriminative localized information.

PPMI UIUC 15Sc MIT67

Deep features

ImageNet [START_REF] Jia | Caffe: Convolutional architecture for fast feature embedding[END_REF] 54. We also compare MANTRA to state-of-the-art works in Table 1. We can notice that the improvement over partbased models, which use weaker features and essentially based on LSSVM [START_REF] Yu | Learning structural svms with latent variables[END_REF], e.g. HoG, is huge. We also provide comparisons to recent methods based on deep features: we report performances with models pre-trained on ImageNet, but also using Places, a large-scale scene dataset recently introduced in [START_REF] Zhou | Learning Deep Features for Scene Recognition using Places Database[END_REF]. As we can verify, Places is bettersuited for scene recognition (performance boost in 15-Scene and MIT67), whereas ImagetNet has an edge over Places for object classification (PPMI). For UIUC, both models present similar performances. In Table 1, we can see that MANTRA can further improve performances over the best deep features (ImageNet or Places) by a large margin on the 4 databases, e.g. 8.5 pt on the challenging MIT67 dataset, or 11 pt on PPMI. As mentionned in Section 2, internal representations learned by ConvNets present limited invariance power: learning strong invariance is therefore challeng-ing [START_REF] Zhang | PANDA: Pose Aligned Networks for Deep Attribute Modeling[END_REF]. We show here that the proposed WSL scheme is able to efficiently learn strong invariance by aligning image regions, increasing performances when built upon strong deep features. MANTRA also significantly outperforms MOP-CNN [START_REF] Gong | Multi-scale orderless pooling of deep convolutional activation features[END_REF] which uses VLAD pooling with deep features extracted at different scales. This shows the capacity of our model to seek discriminative part regions, whereas background and non-informative parts are incorporated into image representation in [START_REF] Gong | Multi-scale orderless pooling of deep convolutional activation features[END_REF].

MANTRA Analysis

In this section, we provide an analysis of our method. We study the training time with respect to the number of regions, we show visual results, and compare MANTRA to LSSVM [START_REF] Yu | Learning structural svms with latent variables[END_REF].

Time analysis

The Figure 3 shows the training time required on 1 CPU (2.7 Ghz, 32 Go RAM) to train models on UIUC-Sports and MIT67. Results for 15 Scene and PPMI are reported in supplementary material C.1. Training MANTRA is fast: for example, it takes 1 minute at scale 30% of UIUC, where the training set is composed of 540 images and ∼ 36 000 regions. The training time increases linearly with respect to the number of regions per image. It is the expected behavior, because the most time consuming step of Algorithm 1 is the loss-augmented inference, which is proportional to the size of the latent space when it is solved exhaustively. This confirms that the proposed 1slack cutting plane strategy to solve the optimization problem (section 3.3) is efficient. Comparison to LSSVM As previously mentioned, most of state-of-the-art WSL works are based on DPM [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] or LSSVM [START_REF] Yu | Learning structural svms with latent variables[END_REF]. To highlight model differences between MANTRA and LSSVM, we carry out experiments with the same (deep) features, and evaluate performances on the same splits. For small scales, the choice of a proper region for classification is crucial. In Table 2, we report classification performances for both methods at scale 30%. Results clearly show the superiority of our model: MANTRA outperforms LSSVM by a very large margin, e.g. ∼ 30 pt increase on PPMI and MIT67. In Table 2, we also report the training time. MANTRA training is much faster than LSSVM's: for example, MANTRA is 30 times faster for UIUC Sports. The significant speedup for training MANTRA can be explained by the fact that LSSVM uses CCCP [START_REF] Yuille | The concave-convex procedure[END_REF] to solve the non-convex optimization problem.

UIUC-Sports MIT67

To further analyze the performance gain of MANTRA vs LSSVM, we isolate in Table 2 the impact of the new prediction function (section 3.1) by training MANTRA with CCCP (MANTRA-C), and the non-convex cutting-plane (NCCP) optimization (section 3.3), by training LSSVM with NCCP (LSSVM-N). CCCP leads to slightly better results for LSSVM, because the decomposition proposed by [START_REF] Yu | Learning structural svms with latent variables[END_REF] exploits the structure of the optimization problem. In contrast, MANTRA objective (Eq. ( 5)) does not directly rewrites as a difference of convex (DC) functions. We can still use the generic DC decomposition of an arbitrary function f5 (Theorem 1 of [START_REF] Yuille | The concave-convex procedure[END_REF]) to use CCCP for MANTRA: results in Table 2 show that both optimizations give similar performances, because the decomposition is not driven by the structure of the problem, while MANTRA CCCP being significantly slower. The conclusion of this study is that the superiority of MANTRA vs LSSVM is due to the new prediction function. Visual analysis We illustrate in Figure 4 the form of the regions corresponding to h + b and h - b templates for the badminton classifier in the UIUC-Sports dataset. On top row,

s b (h - b ) = 0.1 s b (h - b ) = 0.3 s b (h - b ) = 0.2 s b (h - b ) = -0.7 s b (h - b ) = -0.6 s b (h - b ) = -0.6

Ranking

We evaluate our ranking model (section 4.2) for 2 different applications: action classification (VOC 2011), and object recognition (VOC 2007). The performances on the 2 datasets are evaluated with a ranking measure (MAP).

Action Classification

Setup The VOC 2011 Action Classification dataset includes 10 different action classes. We use standard (∼2400-dim) poselets as region features [START_REF] Behl | Optimizing average precision using weakly supervised data[END_REF]. We compare WSL models optimizing accuracy, i.e. LSSVM-Acc and MANTRA-Acc, and models explicitly optimizing AP, i.e. MANTRA-AP and LAPSVM [START_REF] Behl | Optimizing average precision using weakly supervised data[END_REF]. Since the dataset contains Bounding Box (BB) annotations, we evaluate both ranking (MAP) and detection (average overlap between predicted and ground truth BB) performances. Experiments are carried out on the trainval set in a weakly supervised setup, i.e. without bounding box for training and testing, for 5 random splits (with 80% for training, 20% for testing).

Results As shown in Table 3, MANTRA-Acc outperforms LSSVM-Acc by ∼ 6 pt, again validating the relevance of the new model introduced in this paper. MANTRA-Acc also performs similarly to LAPSVM [START_REF] Behl | Optimizing average precision using weakly supervised data[END_REF], which is, to the best of our knowledge, the only method that optimizes an AP-based loss function over weakly supervised data. MANTRA-AP can further improve performances over MANTRA-Acc by 7 pt, which confirms the relevance of optimizing AP during training. T-test shows that MANTRA-AP is significantly better than LAPSVM with a risk of 0.1% (see supplementary C.2).

As we can see in Table 3, detection results are strongly correlated to ranking performances: MANTRA-AP also outperforms LAPSVM in terms of detection metric. Ttest also reveals that the difference is significant with a risk of 0.1% (see supplementary C.2). Detection performances also give a quantitative validation that MANTRA is able to localize semantic parts, here people performing the action. We can interpret the use of the max + min operation as a regularizer of the latent space, which exploits the capacity of h -to witness the absence of a class to find more semantic part predictions h + .

Method

Ranking Note that our protocol differs from [START_REF] Behl | Optimizing average precision using weakly supervised data[END_REF], which evaluates on the test set and uses bounding box annotations. When using the same protocol as in [START_REF] Behl | Optimizing average precision using weakly supervised data[END_REF], LAPSVM reaches 44.3% vs 47.1% for MANTRA-AP. Note that with this protocol, the prediction function used in test is the same for both models.

Impact of hyperparameter C: we show in Figure 5 performance variations vs C. We can observe that all methods reach optimal scores for large values: cross-validation on the train set always leads to C = 10 4 or 10 5 optimal values. We show in Figure 5b) the results of LAPSVM with NCCP and MANTRA-AP with CCCP. As in Table 2, the superiority of MANTRA is due to the prediction function.

Object Recognition

Finally, we perform experiment on the VOC 2007 database, which is the most famous object recognition benchmark used in the last decade. We extract deep features pre-trained on ImageNet using MatConvNet library [START_REF] Chatfield | Return of the devil in the details: Delving deep into convolutional nets[END_REF]. As in [START_REF] Chatfield | Return of the devil in the details: Delving deep into convolutional nets[END_REF], we take the output of the seventh layer of imagenet-vgg-m-2048, after the ReLU. As done for the multi-class classification (section 5.1.1), we extract deep features at different scales, and combine them with Object-Bank (OB) [START_REF] Li-Jia Li | Object bank: A high-level image representation for scene classification & semantic feature sparsification[END_REF] to have a multi-scale model. We compare our model instantiated for multi-class classification (MANTRA-Acc) and ranking (MANTRA-AP) to state-ofthe-art results.

Results

The performance obtained with deep features computed on the whole image is 77%, which is conform to what is reported in [START_REF] Chatfield | Return of the devil in the details: Delving deep into convolutional nets[END_REF]. As shown in Table 4, MANTRA-Acc based on these features can improve performances by more than 5 pt, reaching 82.6%. MANTRA-AP further significantly improves performances by more than 3 pt, reaching 85.8%, again supporting the relevance of optimizing AP during training. Compared to recent methods, our model also outperforms [START_REF] Oquab | Learning and transferring mid-level image representations using convolutional neural networks[END_REF] and SPP-net [START_REF] He | Spatial pyramid pooling in deep convolutional networks for visual recognition[END_REF], which used a spatial pyramid pooling layer. To the best of our knowledge, the best published score on VOC 2007 is 82.4% [START_REF] Chatfield | Return of the devil in the details: Delving deep into convolutional nets[END_REF], where fine-tuning with a ranking-based objective function is used. MANTRA-AP outperforms this method by more than 3 pt, without fine-tuning and data augmentation. Table 4. Ranking performances on VOC 2007.

Conclusion

This paper introduces a new latent structured output model, MANTRA, which prediction function is based on two latent variables (h + , h -). The intuition behind h -is as follows: for an incorrect output, it seeks negative evidence against it. For a correct output, it prevents from having large negative values for any region, thus h -acts as a latent space regularizer exploiting contextual information. Another important contribution is the MANTRA ranking instantiation, for which efficient solutions are introduced to solve the challenging (loss-augmented) inference problem.

The experiments show that MANTRA outperforms state-of-the art performances on five datasets. We can especially point out the large improvement of the AP ranking optimization. Future works include adapting MANTRA for other structured visual applications, e.g. semantic segmentation or metric learning [START_REF] Law | Fantope regularization in metric learning[END_REF].

8 Figure 1 .

 81 Figure 1. MANTRA prediction maps for library classifier s l a) and cloister classifier sc b), for an image of class library. For each class, MANTRA score is s(h + )+s(h -): h + (red) provides localized evidence for the class, whereas h -(blue) reveals its absence.

Algorithm 1

 1 Cutting Plane Algorithm for training MANTRA Input: Training set {(x i , y i )} i=1,...,N , precision ε, C.

  working set and solve QP 4:

Figure 2 .

 2 Figure 2. Predictive (multi-class) accuracy (%) (values are reported inTable 1 of supplementary material C.1)

Figure 3 .

 3 Figure 3. MANTRA training time (seconds) vs number of regions per image (values are reported in Tab 2 of supp. mat. C.1)

Figure 4 .

 4 Figure 4. Examples of predicted regions for badminton classifier (s b ) on images from badminton class (top) and other classes (bottom). We also report the corresponding scores of each region h - b .

  a) impact of hyperparameter C b) optimization vs prediction function Figure 5. Analysis of ranking performances

Table 1

 1

of supplementary material C.1)

Table 1 .

 1

		5 *	94	88	58.5
	Places [42]	38.6 *	94.1	90.2	68.2
	MOP-CNN [12]	-	-	-	68.9
	Part-based
	SPM [20]	39.1	71.6	81.4	34.4
	Object Bank [22]	-	77.9	80.9	37.6
	RBoW [26]	-	-	78.6	37.9
	DSS [32]	49.4	-	85.5	-
	LPR [30]	-	86.3	85.8	44.8
	IFV + BoP [16]	-	-	-	63.1
	MLrep+IFV [7]	-	-	-	66.9
	[33]	-	86.4	86.0	51.4
	MANTRA	66.2	97.3	93.4	76.6

Performances of MANTRA and comparison to state-ofthe art works ( * our re-implementation).

Table 3 .

 3 Ranking and detection results on VOC 2011 Action. Performances per split are given in supplementary material C.2

i.e. x i is is ranked ahead of x j .

www.mosek.com

MANTRA performances remain steady once C is sufficiently large.

f (w) = fvex(w) + fcave(w) = f (w) + λg(w) -λg(w) where g is a convex function, and λ a positive constant.

Acknowledgments This research was supported by a DGA-MRIS scholarship.


Thibaut Durand
email: thibaut.durand@lip6.fr

Nicolas Thome
email: nicolas.thome@lip6.fr

Matthieu Cord
email: matthieu.cord@lip6.fr

WELDON: Weakly Supervised Learning of Deep Convolutional Neural Networks

In this paper, we introduce a novel framework for WEakly supervised Learning of Deep cOnvolutional neural Networks (WELDON). Our method is dedicated to automatically selecting relevant image regions from weak annotations, e.g. global image labels, and encompasses the following contributions. Firstly, WELDON leverages recent improvements on the Multiple Instance Learning paradigm, i.e. negative evidence scoring and top instance selection. Secondly, the deep CNN is trained to optimize Average Precision, and fine-tuned on the target dataset with efficient computations due to convolutional feature sharing. A thorough experimental validation shows that WELDON outperforms state-of-the-art results on six different datasets.

Introduction

Over the last few years, deep learning and Convolutional Neural Networks (CNN) [22] have become state-of-the-art methods for various visual recognition tasks, e.g. image classification or object detection. To overcome the limited invariance capacity of CNN, bounding box annotations are often used [START_REF] Oquab | Learning and transferring mid-level image representations using convolutional neural networks[END_REF][START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF]. However, these rich annotations rapidly become costly to obtain [START_REF] Blaschko | Tutorial: Visual learning with weak supervision[END_REF], making the development of Weakly Supervised Learning (WSL) models appealing.

Recently, there have been some attempts for WSL training of deep CNNs [START_REF] Oquab | Is object localization for free? weakly-supervised learning with convolutional neural networks[END_REF][START_REF] Papandreou | Modeling local and global deformations in deep learning: Epitomic convolution, multiple instance learning, and sliding window detection[END_REF]. In this context, image annotations consist in global labels, and the training objective is to localize image regions which are the most relevant for classification. In computer vision, the dominant approach for WSL is the Multiple Instance Learning (MIL) paradigm [START_REF] Dietterich | Solving the multiple instance problem with axis-parallel rectangles[END_REF]: an image is considered as a bag of regions, and the model seeks the max scoring instance in each bag [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF][START_REF] Russakovsky | Objectcentric spatial pooling for image classification[END_REF][START_REF] Parizi | Reconfigurable models for scene recognition[END_REF][START_REF] Bilen | Object classification with latent window parameters[END_REF][START_REF] Sun | Learning discriminative part detectors for image classification and cosegmentation[END_REF][START_REF] Sharma | Discriminative spatial saliency for image classification[END_REF][START_REF] Durand | Incremental learning of latent structural svm for weakly supervised image classification[END_REF]. Recently, relaxations of standard MIL assumptions have been introduced in the context of Latent SVM models and shallow architectures [START_REF] Li | Multiple instance learning for soft bags via top instances[END_REF][START_REF] Parizi | Automatic discovery and optimization of parts for image classification[END_REF][START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF], showing improved recognition performances on various object and scene datasets. In this paper, we propose a new model for WEakly supervised Learning of Deep cOnvolutional neural Networks (WELDON), which is illustrated in Figure 1. WELDON is trained to automatically select relevant regions from images annotated with a global label, and to perform end-toend learning of a deep CNN from the selected regions. The ultimate goal is image classification (or ranking). We call this setting weakly-supervised, because the localization step only exploits global labels.

Regarding WSL, WELDON is dedicated to selecting two types of regions, adapted from [START_REF] Li | Multiple instance learning for soft bags via top instances[END_REF][START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF][START_REF] Parizi | Automatic discovery and optimization of parts for image classification[END_REF] to deep networks: green regions in Figure 1 correspond to areas with top scores, i.e. regions which best support the presence of the global label. On the contrary, red regions incorporate negative evidence for the class, i.e. are the lowest scoring areas. Our deep WSL model is detailed in section 3.

Regarding training, the model parameters are optimized using back-propagation with standard classification losses, but we also adapt the learning to structured output ranking. We design a network architecture which enables fast region feature computation by convolutional sharing. The network is initialized from deep features trained on ImageNet, and the parameters are fine-tuned on the target dataset.

Related Works & Contributions

The computer vision community is currently witnessing a revolutionary change, essentially caused by Convolutional Neural Networks (CNN) and deep learning. Beyond the outstanding success reached in the context of large scale classification (ImageNet) [22], deep features also prove to be very effective for transfer learning: state-of-the-art results on standard benchmarks are nowadays obtained with deep features as input. Recent studies reveal that performances can further be improved by collecting large datasets that are semantically closer to the target domain [START_REF] Zhou | Learning Deep Features for Scene Recognition using Places Database[END_REF], or by fine-tuning the network with data augmentation [START_REF] Chatfield | Return of the devil in the details: Delving deep into convolutional nets[END_REF].

Despite their excellent performances, current CNN architectures only carry limited invariance properties: although a small amount of shift invariance is built into the models through subsampling (pooling) layers, strong invariance is generally not dealt with [START_REF] Zhang | PANDA: Pose Aligned Networks for Deep Attribute Modeling[END_REF]. Recently, attempts have been made to overcome this limitation. Some methods revisit the BoW model with deep features as local region activations [START_REF] He | Spatial pyramid pooling in deep convolutional networks for visual recognition[END_REF][START_REF] Gong | Multi-scale orderless pooling of deep convolutional activation features[END_REF] or designed BoW layers [2]. The drawback of these models is that background regions are encoded into the final representation, decreasing its discriminative power. Another option to gain strong invariance is to explicitly align image regions, e.g. by using Weakly Supervised Learning (WSL) models.

In the computer vision community, WSL has been predominantly addressed through the Multiple Instance Learning (MIL) paradigm [START_REF] Dietterich | Solving the multiple instance problem with axis-parallel rectangles[END_REF]. In standard MIL modeling, an image is regarded as a bag of instances (regions), and there is an asymmetric relationship between bag and instance labels: a bag is positive if it contains at least one positive instance, and negative if all its instances are negative -i.e. the Negative instances in Negative bags (NiN) hypothesis. MIL models thus perform image prediction through its max scoring region. The Deformable Part Model (DPM) [14] is an instantiation of the MI-SVM model [START_REF] Andrews | Support vector machines for multiple-instance learning[END_REF] for MIL, which is extremely popular for WSL due to its excellent performances for object detection. Extensive works have therefore used DPM and its generalization to structured output prediction, LSSVM [START_REF] Yu | Learning structural svms with latent variables[END_REF], for weakly supervised scene recognition and object localization [START_REF] Kumar | Self-paced learning for latent variable models[END_REF][START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF][START_REF] Russakovsky | Objectcentric spatial pooling for image classification[END_REF][START_REF] Bilen | Object classification with latent window parameters[END_REF][START_REF] Sadeghi | Latent pyramidal regions for recognizing scenes[END_REF][START_REF] Parizi | Reconfigurable models for scene recognition[END_REF][START_REF] Juneja | Blocks that shout: Distinctive parts for scene classification[END_REF][START_REF] Sun | Learning discriminative part detectors for image classification and cosegmentation[END_REF]. Contrarily to these methods built upon handcrafted features, e.g. BoW models [START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF][START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF][START_REF] Avila | Pooling in image representation: the visual codeword point of view[END_REF][START_REF] Goh | Learning Deep Hierarchical Visual Feature Coding[END_REF] or biologically-inspired models [START_REF] Serre | Robust object recognition with cortex-like mechanisms[END_REF][START_REF] Thériault | Extended Coding and Pooling in the HMAX Model[END_REF][START_REF] Thériault | Dynamic scene classification: Learning motion descriptors with slow features analysis[END_REF], recent approaches tackle the problem of WSL training of deep CNNs, e.g. [START_REF] Oquab | Is object localization for free? weakly-supervised learning with convolutional neural networks[END_REF][START_REF] Papandreou | Modeling local and global deformations in deep learning: Epitomic convolution, multiple instance learning, and sliding window detection[END_REF], incorporating a max CNN layer accounting for the MIL hypothesis.

Recently, interesting MIL extensions have been introduced in [START_REF] Yu | ∝svm for learning with label proportions[END_REF][START_REF] Lai | Video event detection by inferring temporal instance labels[END_REF][START_REF] Li | Multiple instance learning for soft bags via top instances[END_REF][START_REF] Parizi | Automatic discovery and optimization of parts for image classification[END_REF][START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF]. All these methods use a bag prediction strategy which departs from the standard max scoring function in MIL, especially due to the relaxation of the common Negative instances in Negative bags (NiN) MIL assumption. In the Learning with Label Proportion (LLP) framework [START_REF] Yu | ∝svm for learning with label proportions[END_REF], only label ratios between ⊕/ instances in bags are provided during training. In [START_REF] Lai | Video event detection by inferring temporal instance labels[END_REF], the LLP method of [START_REF] Yu | ∝svm for learning with label proportions[END_REF] is explicitly applied to MIL problems, in the context of video event detection. LLP is shown to outperform baseline methods (mi/MI-SVM [START_REF] Andrews | Support vector machines for multiple-instance learning[END_REF]), especially by its capacity to relax the NiN assumption. In [START_REF] Li | Multiple instance learning for soft bags via top instances[END_REF], the authors question the NiN assumption by claiming that it is often violated in practice during image annotation: human rather label images based on their dominant concept than on the actual presence of the concept in each subregion. To support the dominant concept annotation, the authors in [START_REF] Li | Multiple instance learning for soft bags via top instances[END_REF] introduce a prediction function selecting the top scoring instances in each bag. Other approaches departs from the NiN assumption by tracking negative evidence of a class with regions [START_REF] Parizi | Automatic discovery and optimization of parts for image classification[END_REF][START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF]: for example, a cow detector should strongly penalize the prediction of the bedroom class. In [START_REF] Parizi | Automatic discovery and optimization of parts for image classification[END_REF], the authors introduce a WSL learning formulation specific to multi-class classification, where negative evidence is explicitly encoded by augmenting model parameters to represent the positive/negative contribution of a part to a class. In [START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF], the idea of negative evidence is formalized by the introduction of a generic structured output latent variable, where the prediction function is extended from max to max+min region scores. The min scoring region accounts for the concept of negative evidence, and is capitalized on for learning a more robust model.

Many computer vision tasks are evaluated with ranking metrics, e.g. Average Precision (AP). In the WSL setting, this is, however, a very challenging problem: for example, no algorithm exists for solving the loss-augmented inference problem with Latent Structural SVM [START_REF] Yu | Learning structural svms with latent variables[END_REF]. In [START_REF] Behl | Optimizing average precision using weakly supervised data[END_REF], LAPSVM is introduced, enabling a tractable optimization by defining an ad-hoc prediction rule dedicated to ranking. In [START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF], the proposed ranking model offers the ability to solve loss-augmented inference with an elegant symmetrization due to the max+min prediction function.

In this paper, we introduce a new model for WSL training of deep CNNs, which takes advantage of recent MIL extensions. The approach the most closely connected to ours is [START_REF] Oquab | Is object localization for free? weakly-supervised learning with convolutional neural networks[END_REF], which we extend at several levels. Our submission therefore encompasses the following contributions:

• We improve the deep WSL modeling in [START_REF] Oquab | Is object localization for free? weakly-supervised learning with convolutional neural networks[END_REF] by incorporating top instance [START_REF] Li | Multiple instance learning for soft bags via top instances[END_REF] and negative evidence [START_REF] Parizi | Automatic discovery and optimization of parts for image classification[END_REF][START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF] insights into our deep prediction function. Contrarily to [START_REF] Parizi | Automatic discovery and optimization of parts for image classification[END_REF][START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF][START_REF] Li | Multiple instance learning for soft bags via top instances[END_REF], we propose an end-to-end training of deep CNNs.

• We improve deep WSL training in [START_REF] Oquab | Is object localization for free? weakly-supervised learning with convolutional neural networks[END_REF] by introducing a specific architecture design which enable an easy and effective transfer learning and fine-tuning. In addition, we adapt our training scheme to explicitly optimize over ranking metrics, e.g. AP.

• We report excellent performances, outperforming state-of-the-art results on six challenging datasets. A systematic evaluation of our modeling and training contributions highlights their importance for training deep CNN models from weak annotations.

WELDON Model

The proposed WELDON model is decomposed into two sub-networks: a deep feature extraction net and a prediction net, as illustrated in Figure 2. The feature extraction net purpose is to extract a fixed-size deep descriptor for each region in the image, while the prediction net outputs a structured output for the whole image. We firstly detail the prediction network, since the main paper contributions are incorporated at this level, mainly by the introduction of novel methods for weakly supervised learning of deep CNNs.

Prediction network design

The prediction net acts on the L5 layer, which is a set of d(= 512) feature maps with n×n (n ≥ 7) spatial neurons. L5 is computed by the feature extraction net (Section 3.2).

a) Transfer layer

The first layer of the prediction network transforms the L5 layer into a layer L6 of size n ×n ×d 1 (d = 4096), as illustrated in Figure 2. This convolutional layer is composed of filters W 6 , each of size 7×7×d. Note that each 7×7 area in L5 in thus mapped to a fixed-size ddimensional vector, so that this transfer layer is equivalent to applying the whole CNN on each of the 7 × 7 region. This architecture design serves two purposes: fast feature computation in regions (see Section 3.2), and transferring W 6 weights from large scale datasets (see Section 4). b) Weakly-Supervised Prediction (WSP) module This is the heart of the proposed method, and is dedicated to selecting relevant regions for properly predicting the global (structured) label associated to each training image.

The WSP module consists in a succession of two layers. The first layer is a linear prediction model W 7 , which is 1 n = n -6 because of the W 6 filter padding. dedicated to providing a (structured output) prediction for each of the n × n spatial cell in L6. This corresponds to a fully connected layer applied to each spatial cell in L6, which we implement using 1 × 1 convolutions, as in [START_REF] Lin | Network in network[END_REF]. The L7 layer is thus of size n × n × C, where C is the size of the structured prediction map, e.g. C is the number of classes for multi-class classification (we detail our structured output instantiations in Section 4).

The second layer of the WSP module is a spatial pooling layer s, which aggregates, for each output c ∈ {1; C}, the score over the n ×n regions into a single scalar value. This give the final prediction layer L8. As mentioned in Section 2, the standard approach for WSL inherited from MIL is to select the max scoring region. We propose to improve this strategy in two complementary directions.

i) Top instances Based on recent MIL insights on learning with top instances [START_REF] Li | Multiple instance learning for soft bags via top instances[END_REF], we propose to extend the selection of a single region to multiple high scoring regions.

Formally, let us denote as h i ∈ {0, 1} the binary variable denoting the selection of the i th region from layer L7, and l 7 i,c the value of the i th region score for output (e.g. class) c.We propose the following aggregation strategy s top , which selects the k highest scoring regions as follows:

s top (L7) = max h n 2 i=1 h i • l 7 i , s.t. n 2 i=1 h i = k (1)
where h = {h i }, i ∈ 1; n 2 , and l 7 i = l 7 i,c , c ∈ {1; C}. Beyond the relaxation of the NiN assumption, which is sometimes inappropriate (see Section 2), the intuition behind s top is to provide a more robust region selection strategy. Indeed, using a single area for training the model necessarily increases the risk of selecting outliers, guiding the training of the deep CNN towards bad local minima.

ii) MinMax layer When using top instances in Eq [START_REF] Andrews | Support vector machines for multiple-instance learning[END_REF] for classifying images, we make use of the most informative regions. Recent studies show that this information can be effectively combined with negative evidence for a class, e.g. using regions which best support the absence of the class [START_REF] Parizi | Automatic discovery and optimization of parts for image classification[END_REF][START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF]. In this submission, we propose to incorporate this negative evidence in our prediction layer using multiple instances, in the same way as for top instances. Therefore, we augment our aggregation strategy with the term s low , which selects the m lowest-scoring regions in an image:

s low (L7) = min h n 2 i=1 h i • l 7 i , s.t. n 2 i=1 h i = m (2)
The final prediction of the network, that we denote as L8, simply consists in summing s top and s low . If we denote as t * c (resp. l * c ) the k top (resp. m lowest) instances selected for output c, the c th output feature L8(c) is:

L8(c) = s top (L7(c)) + s low (L7(c)) = k t * c =1 l 7 t * c + m l * c =1 l 7 l * c (3)
The proposed WSP aggregation scheme in Eq. ( 3) thus generalizes the max+min prediction function in [START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF] in the case of multiple top positive/negative instances.

Feature extraction network design

The feature extraction network is dedicated to computing a fixed-size representation for any region of the input image. When using CNNs as feature extractors, the most naive option is to process input regions independently, i.e. to resize each region to match the size of a full image for CNN architectures trained on large scale databases such as ImageNet (e.g. 224×224). This is the approach followed in R-CNN [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF], or in MANTRA [START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF]. This is, however, highly inefficient since feature computation in (close) neighbor regions is not shared. Recent improvements in SPP nets [START_REF] He | Spatial pyramid pooling in deep convolutional networks for visual recognition[END_REF] or fast R-CNN [START_REF] Girshick | Fast R-CNN[END_REF] process images of any size by using only convolutional/pooling layers of CNNs trained on Ima-geNet, subsequently applying max pooling to map each region into a fixed-size vector. Fully-convolutional networks are also used for semantic segmentation [START_REF] Chen | Semantic image segmentation with deep convolutional nets and fully connected crfs[END_REF]31].

We propose here a different strategy, which is based on a multi-scale sliding window scheme. In the proposed architecture, input images at a given scale are rescaled to a constant size IxI, with I ≥ 224. For all I, we consider regions of size 224 × 224 pixels, so that the region scale is α = 224/I (see details in Table 1 of supplementary 1). Input images are processed with the fully convolutional/pooling layers of CNNs trained on ImageNet, leading to L5 layers of different sizes.

Our multi-scale strategy is close to that of [START_REF] Oquab | Is object localization for free? weakly-supervised learning with convolutional neural networks[END_REF], but the region size is designed to fit a 224×224 pixel area (i.e. 7×7 in L5 layer), which is not the case in [START_REF] Oquab | Is object localization for free? weakly-supervised learning with convolutional neural networks[END_REF]. This is a crucial difference, which enables the weights W6 to the first prediction layer L6 in Figure 2 to be transferred from Ima-geNet, which is capitalized on for defining a training strategy robust to over-fitting, see Section 4.2. We now detail the training of our deep WSL architecture.

Training the WELDON Model

As shown in Figure 2, the WELDON model outputs L8 ∈ R C . This vector represents a structured output, which can be used in a multi-class or multi-label classification framework, but also in a ranking problem formulation.

Training formulation

In this paper, we consider three different structured prediction for WELDON, and their associated loss functions during training.

Multi-class classification

In this simple case, C is the number of classes. We use the usual soft-max activation function on top of L8: P (L8(c)) = e L8(c) / c e L8(c ) , with its corresponding log loss during training.

Multi-label classification

In the case of multiple labels, we use a one-against-all strategy, as [START_REF] Oquab | Is object localization for free? weakly-supervised learning with convolutional neural networks[END_REF]. For C different classes, we train the C binary classifiers jointly, using logistic regression for prediction P (L8(c)) = 1 + e -L8(c) -1 , with its associated log loss 2 .

Ranking: Average Precision We also tackle the problem of optimizing ranking metrics, and especially Average Precision (AP) with our WELDON model. We use a latent structured output ranking formulation, following [START_REF] Yue | A support vector method for optimizing average precision[END_REF]: our input is a set of N training images x = {x i }, i ∈ {1; N }, with their binary labels y i , and our goal is to predict a ranking matrix c ∈ C of size N × N providing an ordering of the training examples (our ranking feature map is detailed supplementary 2.1, Eq (1)). Here, we explicitly denote the output L8(x, c) to highlight the dependence on x.

During training, we aim at minimizing the following loss: ∆ ap (c * , c) = 1 -AP (c * , c) , where c * is the groundtruth ranking. Since AP is non-smooth, we define the following surrogate (upper-bound) loss:

W (x, c * ) = max c∈C [∆ ap (c * , c)+L8(x, c)-L8(x, c * )] (4)
The maximization in Eq (4) is generally referred to as Loss-Augmented Inference (LAI), while inference consists computing ĉ(x) = arg max c∈C L8(x, c). Exhaustive maximization is intractable due to the huge size of the structured 2 Experimentally, hinge loss with linear prediction performs similarly. output space. The problem is even exacerbated in the WSL setting, see [START_REF] Behl | Optimizing average precision using weakly supervised data[END_REF][START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF]. We exhibit here the following result for WELDON (proof in supplementary 2.2): Proposition 1 For each training example, let us denote s(i) = s top (W 7 L6 i ) + s low (W 7 L6 i ) in Eq (3). Inference and LAI for the WELDON ranking model can be solved exactly by sorting examples in descending order of score s(i).

Proposition 1 shows that the optimization over regions, i.e. score s(i), decouples from the maximization over output variables c. This reduces inference and LAI optimization to fully supervised problems. Inference solution directly corresponds to s(i) sorting. For solving LAI with AP loss ∆ ap in Eq (4), we use the exact greedy algorithm of [52] 3 .

Optimization

Given the loss functions given in Section 4.1, WELDON parameters are adjusted using gradient-based methods.

For multi-class and multi-label predictions, error gradients in L8 are well-known. For the ranking instantiation, we have (details in supplementary 3):

∂ ∂W 7 = ∂L8(x, c) ∂W 7 - ∂L8(x, c * ) ∂W 7
where c is the LAI solution. In all cases, error gradient is back-propagated in the deep CNN through chain rule.

Transfer learning & fine-tuning Similarly to other deep WSL models, our whole CNN contains a lot of parameters. The vast majority of weights is located in W 6 (Figure 2), which contains ∼ 10 8 parameters. Training such huge models on medium-size datasets as those studied in this paper (with [10 3 -10 5 ] examples) is highly prone to over-fitting. With a network even bigger than ours, the authors in [START_REF] Oquab | Is object localization for free? weakly-supervised learning with convolutional neural networks[END_REF] address this issue by extensively using regularization during training with dropout and data-augmentation. We propose here to couple these regularization strategies with a two-step learning procedure to limit over-fitting.

In a first training phase, all parameters except those of the WSP prediction module, i.e. W 7 , are frozen. All other parameters, i.e. convolutional layers and W 6 are transferred from CNNs trained on large-scale datasets (Ima-geNet). Note that the transfer for W 6 is fully effective thanks to the carefully designed architecture of our feature extraction network (Section 3.2) and the transfer layer (Section 3.1a)). It is, for example, not possible as it with the architecture in [START_REF] Oquab | Is object localization for free? weakly-supervised learning with convolutional neural networks[END_REF]. Note that W 7 only contains ∼ 104 parameters, and can therefore robustly be optimized in the considered medium-size datasets. 3 Faster (approximate) methods, e.g. [START_REF] Mohapatra | Efficient optimization for average precision svm[END_REF], could also be used.

In a second training phase, starting with W 7 initialized from the first phase, a fine-tuning of all other CNN parameters is achieved. We use dropmap as regularization strategy, consisting in randomly freezing maps in L 6 .

Experiments

Our deep CNN architecture is based on VGG16 [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF]. We implement our model using Torch7 (http://torch.ch/) 4 .

We evaluate our WELDON strategy on several Computer Vision benchmarks corresponding to various visual recognition tasks. While some choose pre-trained deep features according to the target task (like Places features for Scene recognition [START_REF] Zhou | Learning Deep Features for Scene Recognition using Places Database[END_REF]), we knowingly decide with WEL-DON to use only deep features pre-trained on ImageNet whatever the visual recognition task. This is to put to the proof our claim about genericity of our deep architecture.

Absolute comparison with state-of-the-art methods is provided in Section 5.1, while Section 5.2 analyzes the impact of the different improvements introduced in Section 3 and 4 for training deep WSL CNNs.

Experimental Setup In order to get results in very different recognition contexts, 6 datasets are used: object recognition (Pascal VOC 2007 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF], Pascal VOC 2012 [13]), scene categorization (MIT67 [START_REF] Quattoni | Recognizing indoor scenes[END_REF] and 15 Scene [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF]), and visual recognition, where context plays an important role (COCO [START_REF] Lin | Microsoft coco: Common objects in context[END_REF], Pascal VOC 2012 Action [13]).

For MIT67, 15 Scene and VOC 2007, performances are evaluated following the standard protocol. For VOC 2012, evaluation is carried out on the val set (which does not require server evaluation). On COCO dataset, we follow the protocol in [START_REF] Oquab | Is object localization for free? weakly-supervised learning with convolutional neural networks[END_REF], and perform classification experiments. On Pascal VOC 2012 Action, we use the same weakly supervised protocol as in [START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF], with evaluation on the val set.

Overall comparison

Firstly, we compare the proposed WELDON model to state-of-the-art methods. We use the multi-scale WSL model described in Section 3.2, and scale combination is performed using an Object-Bank [START_REF] Li-Jia Li | Object bank: A high-level image representation for scene classification & semantic feature sparsification[END_REF] strategy. For the selection of top/low instances, we use here the default setting of k = m = 3 (Eq (1) and Eq (2) in Section 3.1), for scale α ≤ 70% (Table 1 of supplementary 1). This parameter is analyzed in Section 5.2, showing further improvements by careful tuning. Results for object (resp. scene and context) datasets are gathered in Table 1 (resp. Table 2 andTable 3).

For object datasets, we can show in Table 1 that WEL-DON outperforms all recent methods based on deep features by a large margin. More specifically, the improvement compared to deep features computed on the whole image [START_REF] Chatfield | Return of the devil in the details: Delving deep into convolutional nets[END_REF][START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF] is significant: there is an improvement over VOC 2007 VOC 2012 Return Devil [START_REF] Chatfield | Return of the devil in the details: Delving deep into convolutional nets[END_REF] 82.4 VGG16 (online code) [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF] 84.5 82.8 SPP net [START_REF] He | Spatial pyramid pooling in deep convolutional networks for visual recognition[END_REF] 82.4 Deep WSL MIL [START_REF] Oquab | Is object localization for free? weakly-supervised learning with convolutional neural networks[END_REF] 81.8 MANTRA [START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF] 85.8 WELDON 90.2 88.5

Table 1. mAP results on object recognition datasets. WELDON and state-of-the-art methods results are reported.

the best method [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF] of ∼ 6 pt on both datasets. Note that since we use deep features VGG16 from [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF], the performance gain directly measures the relevance of using a WSL method, which selects localized evidence for performing prediction, rather than relying on the whole image information. Compared to SPP net [START_REF] He | Spatial pyramid pooling in deep convolutional networks for visual recognition[END_REF], the improvement of ∼ 8 pt on VOC 2007 highlights the superiority of region selection based on supervised information, rather than using handcrafted aggregation with spatial-pooling BoW models. The most important comparison is the improvement over other recent WSL methods on deep features [START_REF] Oquab | Is object localization for free? weakly-supervised learning with convolutional neural networks[END_REF][START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF]. Compared to [START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF], the improvement of 4.4 pt on VOC 2007 essentially shows the importance of using multiple instances, and the relevance of an end-to-end training of a deep CNN in the target dataset. We also outperform the deep WSL CNN in [START_REF] Oquab | Is object localization for free? weakly-supervised learning with convolutional neural networks[END_REF], the approach which is the most closely connected to ours, by 6.7 pt on VOC 2012. This big improvement illustrates the positive impact of incorporating MIL relaxations for WSL training of deep CNNs, i.e. negative evidence scoring and top-instance selection. Finally, we can point out the outstanding score reached by WELDON on VOC 2007, exceeding the nominal score of 90%.

15 Scene MIT67 CaffeNet ImageNet [START_REF] Jia | Caffe: Convolutional architecture for fast feature embedding[END_REF] 84.2 56.8 CaffeNet Places [START_REF] Zhou | Learning Deep Features for Scene Recognition using Places Database[END_REF] 90.2 68.2 VGG16 (online code) [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF] 91.2 69.9 MOP CNN [START_REF] Gong | Multi-scale orderless pooling of deep convolutional activation features[END_REF] 68.9 MANTRA [START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF] 93.3 76.6 Negative parts [START_REF] Parizi | Automatic discovery and optimization of parts for image classification[END_REF] 77.1 WELDON (OB) 94.3 78.0 The results shown in Table 2 for scene recognition also illustrate the big improvement of WELDON compared to deep features computed on the whole image [START_REF] Jia | Caffe: Convolutional architecture for fast feature embedding[END_REF][START_REF] Zhou | Learning Deep Features for Scene Recognition using Places Database[END_REF][START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF] and MOP CNN [START_REF] Gong | Multi-scale orderless pooling of deep convolutional activation features[END_REF], a BoW method pooling deep features with VLAD. It is worth noticing that WELDON also outperforms recent part-based methods including negative evidence during training [START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF][START_REF] Parizi | Automatic discovery and optimization of parts for image classification[END_REF]. This shows the improvement brought out by the end-to-end deep WSL CNN training with WELDON. Note that in these scene datasets, deep features trained on Places [START_REF] Zhou | Learning Deep Features for Scene Recognition using Places Database[END_REF] reach much better results than those trained on ImageNet. Therefore, we can expect further performance improvement with WELDON by using stronger feature as input for transfer, before fine-tuning the network to the target dataset.

In Table 3, we show the results in datasets where contextual information is important for performing prediction. On VOC 2012 action and COCO, selecting the regions corresponding to objects or parts directly related to the class is important, but contextual features are also strongly related to the decision. WELDON outperforms VGG16 [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF] by ∼ 8 pt on both datasets, again validating our WSL deep method in this context. On COCO, the improvement is from 62.8% [START_REF] Oquab | Is object localization for free? weakly-supervised learning with convolutional neural networks[END_REF] to 68.8% for WELDON. This shows the importance of the negative evidence and top-instance scoring in our WSP module, which better help to capture contextual information than the standard MIL max function used in [START_REF] Oquab | Is object localization for free? weakly-supervised learning with convolutional neural networks[END_REF]. Finally, note that the very good results in COCO also illustrate the efficiency of the proposed WSL training of deep CNN with WELDON, which is able to deal with this large datasets (80 classes and ∼ 80000 training examples).

VOC 2012 action COCO VGG16 (online code) [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF] 67.1 59.7 Deep WSL MIL [START_REF] Oquab | Is object localization for free? weakly-supervised learning with convolutional neural networks[END_REF] 62.8 WELDON 75.0 68.8

Table 3. WELDON results and comparison to state-of-the-art methods on context datasets.

WELDON Analysis

In this section, we analyze the impact on prediction performances of the different contributions of WELDON given in Section 3 and 4. Our baseline model a) is the WSL CNN model using an aggregation function s=max at the WSP module stage (Figure 2), evaluated at scale α = 30%. It gives a network similar to [START_REF] Oquab | Is object localization for free? weakly-supervised learning with convolutional neural networks[END_REF], trained at a single scale. To measure the importance of the difference between WEL-DON and a), we perform a systematic evaluation on the performance when the following variations are incorporated: The results are reported in Table 4 for object and context datasets with AP evaluation (VOC 2007 and VOC 2012 action), and in Table 5 From this systematic evaluation, we can draw the following conclusions: It turns out that k-m max+min is the best method for various k/m values, showing that negative evidence contains significant information for visual prediction.

• Minimizing an AP loss enables to further improve performances. Interestingly, the same level of improvement is observed when AP optimizing is added to the c) configuration than to the more powerful b)+c) configuration: +3pt on VOC 2012 Action, +1 pt on VOC 2007. This shows that b) and c) are conditionally independent from the AP optimization.

• Fine-tuning favorably impacts performances, with +0.6 pt gain on MIT67 and 15-Scene. Note that the performance level is already high at the b)+c) configuration, making further improvements challenging. These results are obtained with the two-step finetuning proposed in section 4.2. We compare this strategy to a parallel optimization, consisting in jointly updating all network parameters. Performances drop with this parallel procedure, e.g. 73.5% on MIT67.

To further evaluate the impact of the number k top and m low instances, we show in Figure 3 the performance variation (k = m) on MIT67 and 15 Scene. We can see that performances can still be significantly improved on these datasets when k and m increase, although performances decrease for k ≥ 8 on MIT67 (see results in other datasets on supplementary 4). Qualititative analysis of region selection To illustrate the region selection policy performed by WELDON, we show in Figure 5 the top 3 positive (resp. top 3 negative) regions selected by the model in green (resp. red), on the VOC 2007 dataset. We show the results for the ground truth classification model in the first column, with its associated prediction score. We can notice that top positive green regions detect several discriminant parts related to the object class, potentially capturing several instances or modalities (e.g. wheels or airfoil for the car model), whereas negative evidence on red regions, which should remain small, encode contextual information (e.g. road or sky for airplane, or trees for horse). The region selection results are shown for incorrect classification models in the second column, again with the prediction score. We can notice that red regions correspond to multiple negative evidence for the class, e.g. parts of coach strongly penalizes the prediction of the class horse, or seat or handlebar negatively supports the prediction of the sofa category.

Conclusion

In this paper, we introduce WELDON, a new method for training deep CNNs in a weakly supervised manner. Our method exploits to the full extend deep CNN strategy in multiple instance learning framework to efficiently deal with weak supervision. The whole architecture is carefully designed for fast processing by sharing region feature computations, and robust training.

We show the excellent performances of WELDON for WSL prediction on very different visual recognition tasks: object class recognition, scene classification, and images with a strong context, outperforming state-of-the-art results on six challenging datasets. Future works include adapting WELDON for other structured visual applications, e.g. metric learning [START_REF] Law | Fantope regularization in metric learning[END_REF], semantic segmentation.

Figure 1 .

 1 Figure 1. The WELDON model is a deep CNN trained in a weakly supervised manner. To perform image prediction, e.g. classification or ranking, WELDON automatically selects multiple positive (green) + negative (red) evidences on several regions in the image.

Figure 2 .

 2 Figure 2. WELDON deep architecture: our model is composed of 2 sub-networks. The feature extraction net outputs a fixed-size vector for any region in the image, using a multi-scale sliding window mechanism. The prediction net is composed of a transfer layer with weights W6, which enables using networks pre-trained on large-scale datasets for model initialization, and a Weakly-Supervised Prediction (WSP) module, which is the main point studied in this submission. In the proposed WSP module, the spatial aggregation function s combines improvements on the MIL modeling, i.e. top-instance scoring and negative evidence into the training of the full deep CNN.

  b) Use of k top instances instead of the max. We use k = 3. c) Incorporation of negative evidence through max+min aggregation function. When b)+c) are combined, we use m lowest-instances instead of the min, with m = 3. d) Learning the deep WSL with ranking loss, e.g. AP, in the concerned datasets (PASCAL VOC).e) Fine-tuning the network on the target dataset, i.e. using the second training phase in Section 4.2.

•

  Both b) and c) improvements result in a very large performance gain on all datasets, with a comparable impact on performances: ∼ +30 pt on MIT67, ∼ +15 pt on 15-Scene, ∼ +15 pt on VOC 2012 Action and∼ +4 pt on VOC 2007. When looking more accurately, we can notice that max+min leads always to a larger improvement, e.g. is 4 pt above on 15-Scene or VOC 2012 Action and 3 pt on MIT67. • Combining b) and c) improvements further boost performances: +3 pt on MIT67 and VOC 2012 Action, +2 pt on 15-Scene, +1pt on VOC 2007. This shows the complementarity of these two extensions at the aggregation level. We perform an additional experiment for comparing b)+c) and c), by setting the same number of regions (e.g. 6 for k-max and 3-3 for k-m max+min).

Figure 3 .

 3 Figure 3. Multi-class accuracy with respect to the number of top/low instances for MIT67 and 15 Scene at scale α = 30%. Finally, we show in Figure 4 the performance in different configurations, corresponding to sequentially adding the previous improvements in the following order: a), a)+b), b)+c), and b)+c)+d) for VOC 2007 / VOC 2012 / VOC 2012 Action and c)+c)+e) for MIT67 and 15 Scene. On all dataset, we can see the very large improvement from configuration a) to configuration b)+c)+d)/e). The behavior can, however, be different among datasets: for example, the performance boost is sharp from a) to a)+b) on MIT67 (the following improvements being less pronounced), whereas there is a linear increase from a) b)+c)+d) on VOC 2007 and VOC 2012.

Figure 4 .Figure 5 .

 45 Figure 4. Performance variations when the different improvements are incorporated: from the baseline model a) to b), a)+b), b)+c), and b)+c)+d)/e).

Table 2 .

 2 Multiclass accuracy results on scene categorization datasets. WELDON and state-of-the-art methods results are reported.

Table 4 .

 4 for scene datasets. Systematic evaluation of our WSL deep CNN contributions. Object and Context databases with AP evaluation.

	a) max b) +top c) +min d) +AP VOC07 VOC act
	83.6	53.5
	86.3	62.6
	87.5	68.4
	88.4	71.7
	87.8	69.8
	88.9	72.6
	a) max b) +top c) +min d) +FT MIT67 15-Scene
	42.3	72.0
	69.5	85.9
	72.1	89.7
	74.5	90.9
	75.1	91.5

Table 5 .

 5 Systematic evaluation of our WSL deep CNN contributions. Scene databases with multi-class classification evaluation.

FT: fine-tuning.

We will make our code publicly available if accepted.

Acknowledgments This research was supported by a DGA-MRIS scholarship.