A B S T R A C T

Today, with the massive use of smartphones and social networks, images are ubiquitous in our daily lives. To process and exploit this mass of data, it is important to have recognition systems, to analyze and interpret the visual content of the images. This thesis studies the problem of the classification of images, where the goal is to predict if a semantic category -e.g. car, cat -is present in the image according to its visual content.

Several preliminary works have shown that to analyze images of complex scenes, it is important to learn localized representations. To learn localized representations, classical approaches use rich annotations -e.g. bounding boxes, segmentation masks -which are expensive to obtain, whereas in the standard protocol of the classification of images these annotations are not available. To avoid collecting and using rich annotations during training, we have been interested in weakly supervised learning methods. The main idea is to model the missing information in the training data with latent variables. In this thesis, we propose models that simultaneously classify and localize objects, using only global image labels during learning. The contributions of this thesis are threefold: architecture, optimization and experimental results.

The weak supervision significantly reduces the cost of full annotation in many recognition tasks, but it makes learning and recognition more challenging. The key issue is how to aggregate local scores -e.g. regions -into global score -e.g. image. This problem can be seen as a pooling problem. The main contribution of this thesis is the design of new pooling functions for weakly supervised learning. In particular, we propose a pooling function "max + min" which unifies many pooling functions, including several pooling functions introduced in this thesis -SyMIL, MANTRA, WELDON. We prove that the "min" regions provide complementary information to the "max" regions, and can be seen as a negative evidence of the class in the case of multi-class classification. We describe how to use this pooling in a Latent Structured SVM framework as well as in a convolutional networks. Finally, we present a new transfer layer that captures several modalities per class, to enrich the model and to have better prediction.

Our contributions about the optimization are multiple. We show that the objective function of SyMIL can be written as a difference of convex functions, and we present two solvers: one to solve the optimization problem in the primal, and another to solve it in the dual, and which allows to use the kernel trick. For the MANTRA model, we propose a non-convex cutting-plane algorithm to solve the optimization problem. We also show that MANTRA allows to optimize a ranking metric such as the Average Precision during training, if there is a method to optimize this metric in the fully-supervised case.

We experimentally show the interest of our models with respect to state-of-the-art methods, on ten standard image classification datasets, including the large-scale dataset ImageNet. In particular, we show that, with the same representations, our models that focus on discriminating regions are better than state-of-the-art models using a representation extracted over the whole image. We also note that optimizing Average Precision during training is relevant to the datasets evaluated with this metric. To compare iii and analyze the strengths and the weaknesses of commonly used pooling functions, we propose an experimental study on six datasets. Finally, we show that our final model, developed for classification, is also competitive for localization and segmentation.

R É S U M É

Aujourd'hui, avec l'utilisation massive des smartphones et des réseaux sociaux, les images sont omniprésentes dans notre vie quotidienne. Pour traiter et exploiter cette masse de données, il est important d'avoir des systèmes de reconnaissance visuelle, pour analyser et interpréter le contenu visuel des images. Cette thèse s'intéresse au problème de la classification d'images, o ù l'objectif est de prédire si une catégorie sémantique (e.g. voiture, chat) est présente dans l'image, à partir de son contenu visuel.

Plusieurs travaux préliminaires ont montré que pour analyser des images de scènes complexes, il est important d'apprendre des représentations localisées. Pour apprendre des représentations localisées, les approches classiques utilisent des annotations riches (e.g. boites englobantes, masques de segmentation) qui sont couteuses à obtenir, alors que dans le protocole standard de la classification d'images, ces annotations ne sont pas disponibles. Pour ne pas avoir à collecter et utiliser des annotations riches pendant l'apprentissage, nous nous sommes intéressé aux modèles d'apprentissage faiblement supervisé. L'idée est de modéliser les informations manquantes dans les données d'apprentissage avec des variables cachées. Dans cette thèse, nous proposons des modèles qui simultanément classifient et localisent les objets, en utilisant uniquement des labels globaux des images pendant l'apprentissage. Les contributions de cette thèse peuvent être décomposées en trois parties : l'architecture, l'optimisation et les résultats expérimentaux.

L'apprentissage faiblement supervisé permet de réduire le cout d'annotation, mais en contrepartie l'apprentissage est plus difficile. Le problème principal est comment agréger les informations locales (e.g. régions) en une information globale (e.g. image). Ce problème peut être vu comme un problème d'agrégation (pooling). La contribution principale de cette thèse est la conception de nouvelles fonctions de pooling pour l'apprentissage faiblement supervisé. En particulier, nous proposons une fonction de pooling "max+min", qui unifie de nombreuses fonctions de pooling, incluant plusieurs fonctions de pooling introduites dans cette thèse (SyMIL, MANTRA, WELDON). Nous prouvons que les régions "min" apportent une information complémentaire aux régions "max", et peuvent être vues comme des negative evidence de la classe, dans le cas de la classification multi-classes. Nous décrivons comment utiliser ce pooling dans le framework Latent Structured SVM ainsi que dans un réseau de neurones convolutifs. Finalement, nous présentons une nouvelle couche de transfert, qui permet de capturer plusieurs modalités par classe, pour enrichir le modèle et avoir une meilleure prédiction.

Du point de vue de l'optimisation, nos contributions sont multiples. Nous montrons que la fonction objective de SyMIL peut s'écrire comme une différence de fonctions convexes, et nous présentons deux solveurs : un pour résoudre le problème d'optimisation dans le primal, et un autre pour le résoudre dans le dual, et qui permet d'utiliser le kernel trick. Pour le modèle MANTRA, nous proposons un algorithme cutting-plane nonconvexe pour résoudre le problème d'optimisation. Nous montrons aussi que MANTRA permet d'optimiser une métrique d'ordonnancement (ranking) comme l'Average Precision v pendant l'apprentissage, s'il existe une méthode pour optimiser cette métrique dans le cas supervisé.

Expérimentalement, nous montrons l'intérêt nos modèles par rapport aux méthodes de l'état de l'art, sur dix bases de données standard de classification d'images, incluant ImageNet. En particulier, nous montrons que, à représentations égales, nos modèles qui se focalisent sur les régions discriminantes, sont meilleurs que des modèles état de l'art utilisant une représentation extraite sur toute l'image. Nous notons aussi qu'optimiser l'Average Precision durant l'apprentissage est pertinent sur les bases de données évaluées avec cette métrique. Pour comparer et analyser les forces et les faiblesses des fonctions de pooling couramment utilisées, nous proposons une étude expérimentale sur six bases de données. Finalement, nous montrons que notre modèle final, développé pour la classification, est aussi compétitif pour la localisation et la segmentation.

P U B L I C AT I O N S

The material reported in this thesis was the subject of the following publications:

• Thibaut [START_REF] Durand | Image Classification using Object Detectors[END_REF]. "Image Classification using Object Detectors". In: IEEE International Conference on Image Processing (ICIP).

• Thibaut Durand, David Picard, Nicolas Thome, and Matthieu Cord (2014). "Semantic Pooling for Image Categorization using Multiple Kernel Learning". In: IEEE International Conference on Image Processing (ICIP).

• Thibaut Durand, Nicolas Thome, Matthieu Cord, and David Picard (2014). "Incremental Learning of Latent Structural SVM for Weakly Supervised Image Classification". In: IEEE International Conference on Image Processing (ICIP).

• Thibaut [START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF]. "MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking". In: IEEE International Conference on Computer Vision (ICCV).

• Thibaut [START_REF] Durand | WELDON: Weakly Supervised Learning of Deep Convolutional Neural Networks[END_REF]. "WELDON: Weakly Supervised Learning of Deep Convolutional Neural Networks". In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR).

• Thibaut [START_REF] Durand | WILD-CAT: Weakly Supervised Learning of Deep ConvNets for Image Classification, Pointwise Localization and Segmentation[END_REF]. "WILDCAT: Weakly Supervised Learning of Deep ConvNets for Image Classification, Pointwise Localization and Segmentation". In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR).

The following publications are under review:

• Thibaut Durand, Nicolas Thome, and Matthieu Cord (2017b). "SyMIL: MinMax Latent SVM for Weakly Labeled Data". In: IEEE Transactions on Neural Networks and Learning Systems (TNNLS) [Submission].

• Thibaut Durand, Nicolas Thome, and Matthieu Cord (2017a). Pipeline of our image representation using object detectors. . . . . Figure 1. 5 Semantic pooling pipeline for image classification. . . . . . . . . . . 6 wildcat: spatial and class-wise pooling Table 6.1 Generalization of wildcat spatial pooling to other existing Multiple-Instance Learning (MIL) approaches with corresponding parameters. Table 6.2

related work

Classification performances for architectures (a) and (b). . . . . . . Table 6.3

Analysis of multi-map transfer layer. . . . . . . . . . . . . . . . . . . Table 6.4

Ablation study on VOC 2007, VOC 2012 Action and MIT67 . . . . Table 6.5

Multi-scale setup for WILDCAT model. . . . . . . . . . . . . . . . . Table 6.6 MAP results on object recognition datasets. . . . . . . . . . . . . . . Table 6.7

Results on scene, action and fine-grained datasets. . . . . . . . . . . Table 6.8

Classification error on the ILSVRC validation set with single model Table 6.9

Object localization performances (Mean Average Precision (MAP)) on PASCAL VOC 2012 and MS COCO. . . . . . . . . . . . . . . . . Table 6 T oday, the field of computer vision has become ubiquitous in our society, with applications in image understanding, image search, medicine, drones, and selfdriving cars. In particular, visual recognition is a central problem to computer vision research, and its goal is to automatically understand the contents of images. From robotics to information retrieval, many desired applications demand the ability to recognize objects, people, scenes, and activities. To train machines that are able to interpret the visual content of an image, the community has developed many algorithms and representations. The main tasks of visual recognition are image classification, detection and segmentation. In this thesis, we mainly focus on the image classification problem. The goal is to predict if a semantic category is present in the image according to its visual content. This is one of the fundamental problems in computer vision that has a large variety of practical applications.

The image classification problem becomes crucial because image and video data are one of the largest and fastest growing sources of information due to the popularization of digital photography (smartphones, digital cameras, etc.) coupled with the expansion of many social networks and mobile Internet access. For instance, there are 350 million photos uploads per day to Facebook 1 and 80 million to Instagram 2 . There are also 300 hours of video uploaded to YouTube every minute. In 2020, Cisco estimates that 82% of all the web traffic will be video, and that every second, a million minutes of video content will cross the network 3 . To exploit that immense and increasing collection of visual data, we need to annotate each image with semantically rich terms, which is the purpose of image classification. Most of the major technology companies, including Google, Facebook, Microsoft, IBM, Yahoo!, Twitter and Adobe, as well as a quickly growing number of start-ups, initiate research and development projects to deploy image understanding products and services.

For a human, the image classification (or image annotation) problem is easy. Unfortunately for a machine it is challenging, because the machine only "sees" numbers, without semantic meaning. The goal is to map all these numbers (i.e. the digital image) into one or several labels (Figure 1.1). This implies understanding complex semantic meanings based on an image's visual content. The main challenge is that low-level image representations (i.e. the pixels) are not discriminative enough to directly predict semantic-level concepts. [START_REF] Smeulders | Content-Based Image Retrieval at the End of the Early Years[END_REF] calls this problem semantic gap. Bridging the semantic gap requires an image classification model which is able to extract high-level representations from raw image pixels. Moreover a good image classification model must be invariant to the intra-class variations (i.e. appearance variations, see Figure 1.2), while simultaneously retaining sensitivity to the inter-class variations. In the 2000s, most of the image representation models were based on handcrafted features. This approach requires careful engineering and considerable domain expertise to design a feature extractor that transforms the raw image pixels into a feature vector. The most popular model was the Bag of Words (BoW) approach. The BoW model is inspired from textual information retrieval [START_REF] Salton | Introduction to Modern Information Retrieval[END_REF]). The intuition is to represent a document as a histogram of the occurrence rate of words in a dictionary. [START_REF] Ma | NeTra: A toolbox for navigating large image databases[END_REF] was the first to adapt BoW for visual recognition in the NeTra toolbox, to represent an image as a bag of visual words based on color descriptors. This method was popularized by [START_REF] Sivic | Video Google: A Text Retrieval Approach to Object Matching in Videos[END_REF], which employs Scale-Invariant Feature Transform (SIFT) local features.

Since AlexNet [START_REF] Krizhevsky | ImageNet Classification with Deep Convolutional Neural Networks[END_REF] won the ImageNet Large Scale Visual Recognition Challenge (ILSVRC) [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF] by the receptive field representation proposed by [START_REF] Hubel | Receptive fields, binocular interaction and functional architecture in the cat's visual cortex[END_REF]. Then the LeNet architecture [START_REF] Lecun | Backpropagation Applied to Handwritten Zip Code Recognition[END_REF][START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF]) developed in the 1980s and 1990s was the first successful application of ConvNets for digit recogniton. But the big ConvNet success was only possible a few decades later, and can be explained by two factors:

• a large amount of available labeled data to avoid over fitting. The ILSVRC classification dataset has 1.2M training images distributed in 1,000 classes.

• the use of Graphics Processing Units (GPUs), which enables training networks 10 or 20 times faster than with Central Processing Units (CPUs).

A deep ConvNet applies several stages of non-linear transformations to an input image, where each stage transforms its input representation into a higher-level one. It learns a hierarchy of representations with an increasing level of abstraction. Most of the stages are composed of convolutions and non-linear activation functions. Contrarily to handcrafted representations, the parameters of these layers are learned from labeled data by optimizing a task-specific objective function.

Motivations

Designing a robust image classification model requires techniques from both computer vision and machine learning fields. While computer vision focuses on representing the image content, machine learning creates statistical models that relate the image content to the semantic annotations.

In this manuscript, we are interested in learning localized representations for image classification. An important drawback of BoW with Spatial Pyramid Matching (SPM) and ConvNet representations is that they are limited by the lack of ability to be spatially invariant to the input image. Because of their design, these representations are robust to local deformations, but not to strong deformations. Moreover, they encode the whole image, so the final representation contains both discriminative (e.g. objects) and non-discriminative (background) information. Encoding background regions in the representation decreases its discriminative power, because background regions introduce "noise". An approach to build translation and scale invariant representations is to use only the object regions to compute the final representation. The intuition is that if we know where to look, recognizing the objects should be easier. (Russakovsky, Y. Lin, et al. 2012) reports a proof of concept, where the authors observe a large improvement of classification performances when the representations are computed on the ground truth object bounding boxes. This validates the fact that learning localized representations, which are spatially invariant, is relevant for image classification.

Similarly, [START_REF] Oquab | Learning and Transferring Mid-Level Image Representations using Convolutional Neural Networks[END_REF] shows that using bounding box supervision is highly beneficial for object classification in cluttered and complex scenes. Indeed, most deep ConvNet architectures are learned on ImageNet, where the objects are centered in the image (first row of Figure 1.3). To use pre-trained deep ConvNet architecture on complex images with non-centered objects as in PASCAL VOC and MS COCO datasets (second and third rows of Figure 1.3), [START_REF] Oquab | Learning and Transferring Mid-Level Image Representations using Convolutional Neural Networks[END_REF] uses bounding box supervision to train object-centric classifiers, and applies the classifiers by searching over different locations in the images. Another alternative is to use pre-trained object detectors, e.g. (N. [START_REF] Zhang | PANDA: Pose Aligned Networks for Deep Attribute Modeling[END_REF] aligns parts with poselet detectors to make human attribute recognition much more efficient. We now present two of our preliminary works [START_REF] Durand | Image Classification using Object Detectors[END_REF]Durand, Picard, et al. 2014) based on object detectors, which motivate the approach developed in this thesis.

In [START_REF] Durand | Image Classification using Object Detectors[END_REF], we use a set of pre-trained object detectors to build a discriminative and compact image representation. As in Object Bank (OB) (L.-J. [START_REF] Li | Object Bank: An Object-Level Image Representation for High-Level Visual Recognition[END_REF], we represent an image based on its response to a large number of pre-trained object detectors. The whole pipeline of our approach is shown in Figure 1.4. The first step uses object detectors to generate heatmaps, where each score indicates whether or not there is an object of interest at the given position and scale in the image. We then pool the heatmaps to build a vector representation. This pooling is applied to the different regions of the spatial pyramid, to keep spatial information.

The previous model uses a set of pre-trained object detectors to represent the content of an image, but the final representation is not invariant to the layout of the objects in the image. To address this problem, we use in (Durand, Picard, et al. 2014) a set of pre-trained object detectors for taking into account the spatial layout, and to align similar semantic regions. The whole pipeline is shown in Figure 1.5. For each category, we use an object detector to predict the region with the maximum likelihood of containing the object. As many regions represent "noise" (because only a few objects are present in an image), we select relevant regions by using a 1 -Multiple Kernel Learning (MKL) [START_REF] Rakotomamonjy | SimpleMKL[END_REF]. [START_REF] Bearman | What's the Point: Semantic Segmentation with Point Supervision[END_REF]). An alternative is to use Weakly Supervised Learning (WSL).

Contributions and Outline

The Weakly Supervised Learning (WSL) is a framework where the model learns to capture aspects of the data that are not labeled in the training data. Learning from weakly labeled data is a very important problem that covers several theoretical and practical aspects towards the development of powerful learning machines. On the one hand, relaxing the requirement of expensive manual and accurate annotations of training data offers the possibility to build large scale databases at reasonable cost. For example, in the computer vision field, annotating images with a global label makes it possible to build databases containing several millions of examples, whereas annotations at the pixel level (e.g. segmentation mask) are much more expensive, which explains why only moderatesize datasets are available [START_REF] Bearman | What's the Point: Semantic Segmentation with Point Supervision[END_REF]. On the other hand, handling weakly labeled data generally requires to expand the representation space with latent variables to model hidden factors and compensate for the weak supervision. In this manuscript, we focus on the WSL setting where the model simultaneously classifies and locates objects given only image-level annotations for training.

In brief, the weak supervision significantly reduces the cost of full annotation in many recognition tasks, but it makes learning and recognition more challenging. The key issue of WSL is to find how to pool the local (i.e. region) scores into global (i.e. image) score. The central contribution of this thesis is the design of new pooling functions for WSL. Based on these pooling functions, we propose deep ConvNet architectures to perform image classification and learn discriminative regions from images annotated with a global label.

• symil: minmax latent svm for weakly labeled data. We also analyze the selected instances of both symmetric and asymmetric approaches.

• mantra: minimum maximum latent structural svm. Chapter 4 introduces a novel WSL framework which extends SyMIL (Chapter 3) to structured output prediction. Our new structured output latent variable model, called MANTRA, is based on negative evidence pooling: the prediction function relies on a pair of latent variables that provides positive (resp. negative) evidence for a given category. We propose two instantiations of our model: multi-class classification and ranking. The content of this chapter is based on [START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF].

• weldon: negative evidence for wsl of deep structured models. Chapter 5 describes how to integrate the negative evidence pooling of Chapter 4 in a deep architecture, to have an end-to-end training model. The architecture design enables an efficient transfer learning and fine-tuning. This chapter also introduces a spatial pooling function, based on multiple regions, which generalizes the MANTRA pooling. The content of this chapter is based on [START_REF] Durand | WELDON: Weakly Supervised Learning of Deep Convolutional Neural Networks[END_REF].

• wildcat: spatial and class-wise pooling. I n this manuscript, we are interested in Weakly Supervised Learning (WSL) for visual recognition. We first present different strategies to extract image representation. We then introduce standard WSL methods, which automatically learn the locations of the objects with image-level labels only. Finally, we give an overview of deep convolutional network architectures for WSL.

Notation We note x ∈ X an input and y ∈ Y an output, where X is the input space and Y is the output space. We note D = {(x i , y i )} N i=1 ∈ (X × Y ) N the training dataset of N examples made up of independent and identically distributed (i.i.d.) samples from a data generating distribution p data , i.e. (x i , y i ) ∼ p data for all i. We note w the vector of parameters.

Visual Representations

In this section, we present two strategies to extract image representations: Bag of Words (BoW) and deep architectures. The BoW approach was the state-of-the-art model for image classification in the 2000s. This is a handcrafted representation, i.e. it is manually designed and relies on expert knowledge. Since 2012, the Convolutional Network (ConvNet) is becoming the state-of-the-art model for image classification. Contrary to the BoW representations, the ConvNet representations are learned from training data.

Handcrafted Representation: Bag of Words

The Bag of Words (BoW) model is inspired from textual information retrieval [START_REF] Salton | Introduction to Modern Information Retrieval[END_REF]). The concept is to represent a document as a histogram of occurrence rates of words from a dictionary. [START_REF] Ma | NeTra: A toolbox for navigating large image databases[END_REF] was the first to adapt BoW for visual recognition in the NeTra toolbox, to represent an image as a bag of visual words. Then, [START_REF] Fournier | RETIN: A Content-Based Image Indexing and Retrieval System[END_REF]) extended this approach with Gabor filters. This method was popularized by [START_REF] Sivic | Video Google: A Text Retrieval Approach to Object Matching in Videos[END_REF], which employs Scale-Invariant Feature Transform (SIFT) local features. To represent an image, the model performs a series of three consecutive steps:

1. Local feature extraction. The local descriptors are extracted uniformly across the image using a uniform grid, which may be overlapping and have multiple scales.

The most popular local descriptor is the SIFT [START_REF] Lowe | Distinctive Image Features from Scale-Invariant Keypoints[END_REF], because it is invariant to various image transformations, such as geometric and photometric transformations, which are essential when addressing image classification problems.

2.

Coding. The coding step encodes the local descriptors as a function of the dictionary visual words, and outputs visual codes. To learn a visual dictionary, the most popular approach for image categorization is the k-means clustering algorithm [START_REF] Lloyd | Least Squares Quantization in PCM[END_REF]. The historical coding function is the hard assignment coding. To reduce the quantization errors and ambiguity resulting from the hard quantization, [START_REF] Gemert | Visual Word Ambiguity[END_REF] proposes the soft assignment. To keep more information, several methods propose to encode the distance in vectorial form: Fisher Vectors (FV) (Perronnin et al. 2007), Super-Vector Coding (SVC) (X. [START_REF] Zhou | Image Classification Using Super-vector Coding of Local Image Descriptors[END_REF], Vector of Locally Aggregated Descriptors (VLAD) method [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF]) and its generalization Vector of Locally Aggregated Tensors (VLAT) [START_REF] Picard | Improving Image Similarity With Vectors of Locally Aggregated Tensors[END_REF]. The visual dictionary contains visual words which are used to project local descriptors into another feature space for the subsequent step in the BoW pipeline.

3.

Pooling. The pooling step constructs a single vectorial representation (or signature) from the set of local visual codes across the whole image. The standard pooling function is the average pooling (or sum pooling) [START_REF] Sivic | Video Google: A Text Retrieval Approach to Object Matching in Videos[END_REF]. Another popular method is the max pooling. [START_REF] Boureau | A theoretical analysis of feature pooling in vision algorithms[END_REF] observes that the best pooling function may be an operation between average and max pooling. To incorporate spatial information, [START_REF] Lazebnik | Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories[END_REF]) introduces the Spatial Pyramid Matching (SPM). In another way, [START_REF] Avila | Pooling in Image Representation: the Visual Codeword Point of View[END_REF] introduces BossaNova (BN), where the standard scalar pooling is replace by a vectorial pooling to capture higher-order statistics. The image representation has the same dimensionality across all the images of possibly different sizes. Then, the final representation is normalized.

The global aim is gaining invariance to nuisance factors (locations of the objects, changes in the background, small changes in appearance, etc.), while preserving the discriminating power of the local descriptors. To predict labels, the common approach is to use these representations to train a classifier with supervised learning algorithms. A classifier is a function that maps the representations to one of the possible categories. The most popular classifiers used in computer vision are k-Nearest Neighbors (k-NN) [START_REF] Cover | Nearest Neighbor Pattern Classification[END_REF],

Decision Trees [START_REF] Breiman | Classification and regression trees[END_REF], Support Vector Machine (SVM) (B. E. [START_REF] Boser | A Training Algorithm for Optimal Margin Classifiers[END_REF][START_REF] Vapnik | The Nature of Statistical Learning Theory[END_REF] and neural networks, which are presented in the next section.

Learned Representation: Deep ConvNets

In 2012, AlexNet, a deep Convolutional Network (ConvNet) architecture proposed by [START_REF] Krizhevsky | ImageNet Classification with Deep Convolutional Neural Networks[END_REF], has emerged as a competitive method for classifying large-scale image datasets with huge amounts of training data, convincingly winning the ImageNet Large Scale Visual Recognition Challenge (ILSVRC) [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF]. In this section, we briefly present the ConvNet, then how to learn it and finally its applications to visual recognition.

Convolutional Networks

The Convolutional Network (ConvNet) (also known as Convolutional Neural Network or CNN) is a type of feedforward network that uses convolution in at least one of its layers. This model is called feedforward because information flows strictly in the forward direction, from the input units, through hidden units, if any, and finally to output units. When feedforward neural networks are extended to include feedback connections, they are called Recurrent Neural Networks (RNNs) [START_REF] Rumelhart | Learning representations by back-propagating errors[END_REF].

The convolution layer is the core layer of deep ConvNets. The convolution exploits spatially local correlation by enforcing a local connectivity pattern between units of adjacent layers. Standard ConvNet architectures are built by stacking convolutional layers followed by non-linearities, and possibly introducing pooling layers to control the computational complexity of the architecture.

ConvNets are typically represented by composing together many different functions or layers. For example, a feedforward network with n layers can be written

f w (x) = f w n ( f w n-1 (. . . f w 2 ( f w 1 (x)))) (2.1)
where x is the input, w = [w 1 , . . . , w n ] is the vector of ConvNet parameters, f w k is the k-th layer and w k is the vector of parameters of the k-th layer. The model is associated with a directed acyclic graph describing how the layers are composed together. We note y the output of the network y = f w (x), and h k = f w k (h k-1 ) the output of the k-th layer, and h 0 = x.

The goal of a ConvNet is to approximate some function f . For example, for a classification problem, the ConvNet maps an input to a category. In general, for an input-output pair (x, y), a ConvNet defines a mapping y = f w (x), and learns the value of the parameters w that results in the best function approximation of f with respect to a loss function L such that L(y , y) > 0 measures the disagreement between a ground-truth label y and a output y.

Learning ConvNets with SGD & Back-propagation

The problem of learning ConvNet reduces to an optimization problem of the general form w = arg min w J (w) where J usually combines the empirical loss L [START_REF] Vapnik | Principles of risk minimization for learning theory[END_REF]) of all training examples and a regularization penalty R J

(w) = 1 N N ∑ i=1 L(y i , f w (x i )) + R(w) (2.2)
The regularization term is used to control the complexity of the model and to prevent overfitting. It can also encode some a priori about the function f w . The 2 regularization (R(w) = 1 2 w 2 2 ) is a common regularizer for ConvNets. We now explain how to solve this optimization problem with Stochastic Gradient Descent (SGD) and back-propagation. Solving this optimization problem is difficult, because the loss function is a non-convex function of the model parameters. The gradient descent requires to compute the gradient of the function J , so in the following of this section, we assume that f w , L and R are differentiable with respect to the model parameters w. We assume that we can calculate the Jacobian matrices ∂h k ∂h k-1 and ∂h k ∂w k for each layer k ∈ {1, . . . , n}.

Stochastic gradient descent Stochastic Gradient Descent (SGD) and its variants are probably the most used optimization algorithms for machine learning in general and for deep learning in particular. The gradient descent method is a common way to minimize an objective function J of parameters w ∈ R d by updating the parameters in the opposite direction of the gradient of the objective function

≈ ∂ J (w) ∂w = ∂ ∂w 1 m m ∑ i=1 L(y I(i) , f w (x I(i) )) + R(w) (2.3)
2. updating the parameters w in the direction of the negative gradient

w = w -η ∂ J (w) ∂w (2.4)
where η is the learning rate or step size.

The learning rate η is a critical hyper-parameter. If it is too high, the optimization may not converge or even diverge. If it is too low, learning will take too long. The most important property of SGD is that computation time per update does not grow with the number of training examples. This allows convergence even when the number of training examples becomes very large.

Several approaches have been proposed to accelerate the convergence of SGD. [START_REF] Polyak | Some methods of speeding up the convergence of iteration methods[END_REF][START_REF] Sutskever | On the importance of initialization and momentum in deep learning[END_REF]) introduce a momentum to accumulate an exponentially decaying moving average of past gradients and to keep moving in their directions. As the learning rate is a crucial hyper-parameter, different algorithms have been proposed to automatically adapt it e.g. AdaGrad [START_REF] Duchi | Adaptive Subgradient Methods for Online Learning and Stochastic Optimization[END_REF], Adadelta (M. D. Zeiler 2012), RMSProp [START_REF] Tieleman | RMSprop Gradient Optimization[END_REF] and Adam [START_REF] Kingma | Adam: A Method for Stochastic Optimization[END_REF].

Back-propagation

To train a feedforward neural network f w with SGD, we must compute the gradient ∂ J (w) ∂w (Equation 2.3). The difficult step is the computation of the gradient ∂L(y , f w (x)) ∂w for a given example x, and its output y . We need to compute the gradient w.r.t. the parameters in each layer. Using the chain rule, the final gradient is the matrix product of all the Jacobians

∂L(y , f w (x)) ∂w l = ∂L(y , f w (x)) ∂h n n ∏ k=l+1 ∂h k ∂h k-1 ∂h l ∂w l (2.5)
The back-propagation [START_REF] Rumelhart | Learning representations by back-propagating errors[END_REF]) is a recursive algorithm that computes the chain rule with a specific order of operations that is highly efficient.

Modern ConvNet Architectures for Image Classification

We now present the most important ConvNet architectures. Since 2012, ConvNets have become popular with the large win of AlexNet [START_REF] Krizhevsky | ImageNet Classification with Deep Convolutional Neural Networks[END_REF] to the competition ImageNet Large Scale Visual Recognition Challenge (ILSVRC) 20121 . AlexNet significantly outperformed the second runner-up based on handcrafted representation (top 5 error of 16% compared to runner-up with 26% error). The network consists of eight learned layers (five convolutional and three fully-connected) that map image pixels to the semantic-level (see Figure 2.1). Then, similar architectures were proposed to improve AlexNet: ZF Net (M. D. Zeiler and Fergus 2014) (winner of the ILSVRC 2013 classification challenge), Overfeat [START_REF] Sermanet | Overfeat: Integrated recognition, localization and detection using convolutional networks[END_REF]), vgg-s, vgg-m, vgg-f (Chatfield et al. 2014) and CaffeNet [START_REF] Jia | Caffe: Convolutional Architecture for Fast Feature Embedding[END_REF].

In 2014, Simonyan and Zisserman show that the depth of the network is a critical component for good performance [START_REF] Simonyan | Very Deep Convolutional Networks for Large-Scale Image Recognition[END_REF]. They introduced the very deep VGG16, a 16 layers ConvNet architecture (see Figure 2.1). A downside of the VGG16 is that it is more expensive to evaluate and uses a lot more memory and parameters (138M).

To reduce the number of parameters, (Szegedy, Liu, et al. 2015) introduces the GoogLeNet, that won the ILSVRC 2014 classification challenge. The main contribution is the development of the Inception module that dramatically reduces the number of parameters in the network (7M, compared to AlexNet with 60M). GoogLeNet (22 layers) is deeper than VGG16 and uses a Global Average Pooling (GAP) instead of fully-connected layers at the top of the ConvNet, eliminating a large amount of parameters. Except the fully-connected of the last layer used for classification, all the learned layers are convolution layers Figure 2.1.

The next step is to learn deeper models than VGG16 and GoogLeNet by adding more layers. But this is not possible in practice because of the vanishing/exploding gradients problem [START_REF] Bengio | Learning Long-term Dependencies with Gradient Descent is Difficult[END_REF][START_REF] Glorot | Understanding the difficulty of training deep feedforward neural networks[END_REF]. To overcome this problem and to learn ConvNets with several hundreds of layers, [START_REF] He | Deep Residual Learning for Image Recognition[END_REF]) builds residual networks (ResNet) by using residual blocks. The residual block uses shortcut connection that skips one or more layers. The authors also show that the residual blocks combined with batch normalization [START_REF] Ioffe | Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift[END_REF]) make the training easier. Like GoogLeNet, the only learned layers are convolution layers. The ResNets won both ILSVRC & MS COCO2 2015 competitions.

Learning deep architecture The evolution of the deep ConvNet architectures shows that the network architecture is very important to perform accurate predictions. The previous architectures were manually designed with some a priori. We went from feature engineering (e.g. BoW) to network engineering. The next step is to automatically learn the network architecture. Note that learning deep network architecture is a challenging task because the number of possible network architectures increases exponentially with the number of layers in the network. Recently, some works propose different methods to learn automatically the network architecture. [START_REF] Srivastava | ProNet: Learning to Propose Object-Specific Boxes for Cascaded Neural Networks[END_REF] introduces the highway networks, which utilize a learnable gating mechanism to automatically learn some connections between layers. [START_REF] Kulkarni | Learning the Structure of Deep Architectures Using L1 Regularization[END_REF] proposes a method to automatically select the number of units in fully-connected layers, by using a 1 regularization. So far, the most general approach is the convolutional neural fabrics [START_REF] Saxena | Convolutional Neural Fabrics[END_REF]. The authors propose a fabric that embeds an exponentially large number of architectures. The fabric consists of a 3D trellis that connects response maps at different layers, scales, and channels with sparse local connectivity patterns.

Transfer Learning & Applications of Deep ConvNets

Training an entire ConvNet from scratch (with random initialization) on large dataset is difficult, because it requires a lot of labeled training images and computational resources (e.g. GPU). For instance, standard ConvNets take about two weeks to train on ImageNet, with only one GPU. To have models easily available, some people release pre-trained models. A key success of the ConvNets is that the learned representations (or features) on ImageNet are both discriminative and generic, so they can be efficiently transfered to other (small) datasets.

Transfer learning We now present the two common transfer learning strategies.

• ConvNet as feature extractor. This strategy is to use the representations of a ConvNet pre-trained on ImageNet to train a classifier for the new dataset. To achieve this, we take a ConvNet pre-trained on ImageNet, and we remove the last fully-connected layer (also called classification layer) because it represents the 1000 class scores of ImageNet. Then we treat the rest of the ConvNet as a fixed feature extractor for the new dataset. These features are called deep features (or CNN codes). It is important for performance that these features are extracted after their activation function. Once the deep features for all the images are extracted, we train a classifier (e.g. SVM) on the new dataset [START_REF] Chatfield | Return of the Devil in the Details: Delving Deep into Convolutional Nets[END_REF][START_REF] Razavian | CNN features off-the-shelf: an astounding baseline for recognition[END_REF]).

• Fine-tuning. The intuition is to learn a ConvNet starting from a "good" initialization, i.e. initialized with the weights of a model pre-trained on ImageNet. The common way to achieve this, is to replace and retrain the classifier layer on top of the ConvNet on the new dataset, but to also fine-tune the weights of the pre-trained network by continuing the back-propagation. It is possible to fine-tune all the layers of the ConvNet, or it is possible to keep some of the earlier layers fixed (due to overfitting concerns) and only fine-tune some higher-level layers of the network (Azizpour, A. S. [START_REF] Azizpour | Factors of Transferability for a Generic ConvNet Representation[END_REF].

Experimentally, we observe that the fine-tuning strategy has better performances than the feature extractor strategy. Unfortunately, the fine-tuning strategy requires computational resources because it needs to evaluate several forward and backward passes. On the contrary, the feature extractor strategy requires only one forward pass for each image.

Applications Since 2012, the ConvNets have become the state-of-the art model for large scale classification. They won the ILSVRC [START_REF] Zeiler | ADADELTA: An Adaptive Learning Rate Method[END_REF], 2013, 2014[START_REF] Girshick | Fast R-CNN[END_REF][START_REF] Szegedy | that combines both ResNet and Inception architectures. Better results can be obtained by learning ensemble of models[END_REF]challenges (Krizhevsky et al. 2012;;M. Zeiler et al. 2013;Szegedy, Liu, et al. 2015;[START_REF] He | Deep Residual Learning for Image Recognition[END_REF]. They also show that they can be efficiently transfered to small and medium size datasets (Azizpour, A. S. Razavian, et al. 2016). The learned representation are generics and are state-of-the art methods for different classification problems such as object classification [START_REF] Chatfield | Return of the Devil in the Details: Delving Deep into Convolutional Nets[END_REF][START_REF] Oquab | Learning and Transferring Mid-Level Image Representations using Convolutional Neural Networks[END_REF][START_REF] He | Spatial Pyramid Pooling in Deep Convolutional Networks for Visual Recognition[END_REF][START_REF] Oquab | Is object localization for free? -Weakly-supervised learning with convolutional neural networks[END_REF], scene classification [START_REF] Gong | Multi-scale Orderless Pooling of Deep Convolutional Activation Features[END_REF][START_REF] Zhou | Learning Deep Features for Scene Recognition using Places Database[END_REF]Bolei Zhou, Khosla, et al. 2016), action recognition [START_REF] Chéron | P-CNN: Pose-based CNN Features for Action Recognition[END_REF][START_REF] Gkioxari | Contextual action recognition with R* CNN[END_REF]Diba, Pazandeh, et al. 2016), fine-grained classification (Y. [START_REF] Wang | Mining Discriminative Triplets of Patches for Fine-Grained Classification[END_REF][START_REF] Huang | Part-Stacked CNN for Fine-Grained Visual Categorization[END_REF][START_REF] Reed | Learning Deep Representations of Fine-grained Visual Descriptions[END_REF], food recognition (Xin Wang et al. 2015;F. Zhou et al. 2016), etc.

The ConvNets have been successfully applied on other standard computer vision applications such as object detection, semantic segmentation. The goal of the object detection task is to predict a bounding box for each object present in the image. The most popular models are R-CNN (R. [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF], Fast R-CNN (Ross Girshick 2015), Faster R-CNN [START_REF] Ren | Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks[END_REF], R-FCN (Dai, Y. Li, et al. 2016), MultiPathNet [START_REF] Zagoruyko | A MultiPath Network for Object Detection[END_REF] and YOLO [START_REF] Redmon | You Only Look Once: Unified, Real-Time Object Detection[END_REF]. The ConvNets are also used for semantic segmentation, where the goal is to predict a label for each pixel of the image. Different architectures have been proposed to predict segmentation masks such as the Fully Convolutional Network (FCN) [START_REF] Long | Fully Convolutional Networks for Semantic Segmentation[END_REF], DeepLab (L. [START_REF] Chen | Semantic Image Segmentation with Deep Convolutional Nets and Fully Connected CRFs[END_REF] and CRFasRNN [START_REF] Zheng | Conditional Random Fields as Recurrent Neural Networks[END_REF]. Similarly, (Pedro O Pinheiro et al. 2015) introduces DeepMask to predict class-agnostic segmentation masks and it can be coupled with SharpMask (Pedro O. [START_REF] Zagoruyko | A MultiPath Network for Object Detection[END_REF] to refine the masks.

Today, the ConvNet-based models yield state-of-the-art performances in many areas of computer vision: object tracking (L. Wang et al. 2015;H. Li et al. 2016), image retrieval [START_REF] Paulin | Local Convolutional Features with Unsupervised Training for Image Retrieval[END_REF][START_REF] Arandjelović | NetVLAD: CNN architecture for weakly supervised place recognition[END_REF], instance segmentation (Z. [START_REF] Zhang | Instance-Level Segmentation with Deep Densely Connected MRFs[END_REF]Dai, He, et al. 2016), contour detection (J. [START_REF] Yang | Object Contour Detection with a Fully Convolutional Encoder-Decoder Network[END_REF], pose estimation [START_REF] Toshev | DeepPose: Human Pose Estimation via Deep Neural Networks[END_REF][START_REF] Gkioxari | Chained Predictions Using Convolutional Neural Networks[END_REF], optical flow estimation [START_REF] Dosovitskiy | Flownet: Learning optical flow with convolutional networks[END_REF], Visual Question Answering (VQA) (H. [START_REF] Xu | Ask, Attend and Answer: Exploring Question-Guided Spatial Attention for Visual Question Answering[END_REF][START_REF] Fukui | Multimodal Compact Bilinear Pooling for Visual Question Answering and Visual Grounding[END_REF]) etc.

Weakly Supervised Learning

Despite excellent performances for image classification, deep ConvNets carry limited invariance properties, i.e. a small shift invariance through pooling layers. This lack of spatial invariance hinders effective transfers on target datasets with strong variations w.r.t. the source datasets. For example, we note a large shift between ImageNet, which essentially contains centered objects, and other common datasets, e.g. PASCAL VOC or MS COCO, containing several objects and strong scale and translation variations (Figure 1.3). [START_REF] Long | Fully Convolutional Networks for Semantic Segmentation[END_REF]) than image-level labels. However, these rich annotations rapidly become costly to obtain, making the development of Weakly Supervised Learning (WSL) models appealing. WSL methods allow to capture unobserved information about the data that is not labeled in the training data. In this thesis, we focus on WSL to learn spatially invariant representations, because we can explicitly align image regions. We now present Multiple-Instance Learning (MIL), which is the most popular WSL framework for computer vision, and WSL methods for structured outputs.

Multiple-Instance Learning & its Extensions

The Multiple-Instance Learning (MIL) is a popular framework for bag classification with binary labels, i.e. the output space is Y = {-1, +1}. The input x is represented as a bag of instances x = {x h } h∈H(x) , where x h is the h-th instance, and H(x) is the set of instance indexes in bag x. H(x) depends on the bag x, because every bag has its own number of instances. To simplify the notation in the following, we write H without the bag dependency when there is no ambiguity. We note Φ(x, h) ∈ R d the vectorial representation of the h-th instance of bag x. For example in Figure 2.2, the bag is the image, and the instances are regions of the image. Because it may be expensive to assign a reliable label to each training instance, only the bag has a label, i.e. we know if an object is present or absent, but we do not know about its location. The important difference to standard supervised learning is that the label is given for the whole bag, but not for the individual instances in a bag (Figure 2.3). Given a training dataset of labeled bags D = {(x i , y i )} N i=1 ∈ (X × Y ) N , the goal is to learn a bag classification function f w : X → Y, where w are the model parameters. We now present the Multiple-Instance Learning (MIL) and its extensions.

Multiple-Instance Learning

The Multiple-Instance Learning (MIL) paradigm [START_REF] Dietterich | Solving the Multiple Instance Problem with Axis-parallel Rectangles[END_REF]) is related to the relationship between bag and instance labels: a bag is positive if it contains at least one positive instance, and negative if it contains only negative instances (Figure 2.3). A classical toy example consists in viewing a bag as set of keys: a bag is labeled positive if it contains a key able to open the door, and negative if none of the keys can. Notice that the information provided by the label is asymmetric in the sense that a negative bag label induces a unique label for every pattern in a bag, while a positive label does not. MIL methods can be categorized into two main paradigms: bag-space methods and instance-space methods.

Supervised learning

Multiple-Instance Learning (MIL) Bag-space methods Bag-space methods treat each bag as a whole entity and train a classifier directly on the bags by making a global representation of bags or extracting discriminative bag-level information from them. Embedded-space methods correspond to methods that embed each bag into a feature space, where standard supervised learning techniques (e.g. SVM) can be applied. First, each bag is mapped to a single feature vector by a mapping function, then a single-instance classifier is trained in the embedded space. Instance-space methods An instance-level classifier is trained to classify positive and negative instances in the instance space, and based on these classifiers a bag-level classifier is derived by aggregation. MIL approaches based on SVMs learn a hyperplane to separate positive and negative instances and perform bag label prediction through its max scoring instance

f w (x) = sign max h∈H w, Φ(x, h) (2.6)
where x is the input bag, and w ∈ R d is a vector of model parameters (or hyperplane).

If the maximum score is positive, then there is at least one positive instance. If the maximum score is negative, then all the instances are negatives. To learn the parameters w, [START_REF] B I B L I O G R A P H Y Andrews | Support Vector Machines for Multiple-Instance Learning[END_REF] adapted SVMs to the MIL problem, and proposed mi-SVM and MI-SVM algorithms. Both these algorithms are max-margin algorithms, which are formulated as mixed integer optimization problems. The main difference between these two algorithms is how the margin is defined. The mi-SVM is based on an instance margin formulation, i.e. it maximizes the margin over all instances labeled with latent labels, while the MI-SVM is based on a bag margin and maximizes the margin over the most positive instance of each positive bag and all instances of the negative bags.

The MI-SVM inspired pioneer works for weakly labeled object detection in the computer vision community. Specifically, the Latent SVM (LSVM) [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF]) solves a "MI-SVM-like" problem, where the instances correspond to sub-part positions of the putative object position. It is worth mentioning that LSVM slightly differs from MI-SVM in the optimization scheme, since only the maximum output latent variable are used for negative examples to solve LSVM optimization problem, whereas all negative instances are used for MI-SVM. Figure 2.4 shows the instances used during training, and the positions of the hyperplane for the standard MIL approaches. We note that the mi-SVM uses all the instances for each bag whereas the LSVM uses a single instance per bag and the MI-SVM uses a single instance for each positive bag, and all the instances for negative bags.

Interesting adaptations of these SVM-like MIL algorithms have been proposed: a solution dedicated to sparse positive bags [START_REF] Bunescu | Multiple Instance Learning for Sparse Positive Bags[END_REF], using deterministic annealing to continuously approximate the problem [START_REF] Gehler | Deterministic Annealing for Multiple-Instance Learning[END_REF]), a convex relaxation with the soft-max loss function [START_REF] Joulin | A convex relaxation for weakly supervised classifiers[END_REF], modeling instance dependencies as in MI-CRF [START_REF] Deselaers | A Conditional Random Field for Multiple-Instance Learning[END_REF], or using a multi-fold MIL procedure [START_REF] Cinbis | Weakly Supervised Object Localization with Multi-fold Multiple Instance Learning[END_REF] to avoid poor local optima.

Multiple-Instance Learning Extensions

Recently, interesting MIL extensions have been introduced in (F. X. [START_REF] Yu | ∝SVM for Learning with Label Proportions[END_REF][START_REF] Lai | Video Event Detection by Inferring Temporal Instance Labels[END_REF]W. Li et al. 2015;[START_REF] Parizi | Automatic discovery and optimization of parts for image classification[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 (NINB) MIL assumption.

In (W. [START_REF] Li | Multiple Instance Learning for Soft Bags via Top Instances[END_REF], the authors question the NINB 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 sub-region. The standard formulation of MIL fails to account that negative bags can also have very noisy instance composition. (W. [START_REF] Li | Multiple Instance Learning for Soft Bags via Top Instances[END_REF] introduces a new formulation, where both positive and negative bags are soft, in the sense that negative bags can also contain few positive instances. To support the dominant concept annotation, the authors introduce In the Learning with Label Proportion (LLP) framework (F. X. [START_REF] Yu | ∝SVM for Learning with Label Proportions[END_REF], only label ratios between positive and negative instances in the bags are provided during training. This problem often occurs in practice. For example, after election, the proportions of votes of each demographic area are released by the government. In [START_REF] Lai | Video Event Detection by Inferring Temporal Instance Labels[END_REF], the LLP method of (F. X. [START_REF] Yu | ∝SVM for Learning with Label Proportions[END_REF]) is explicitly applied to MIL problems, in the context of video event detection. Similarly to top instances approach (W. [START_REF] Li | Multiple Instance Learning for Soft Bags via Top Instances[END_REF], [START_REF] Lai | Video Event Detection by Inferring Temporal Instance Labels[END_REF] assumes that each positive video contains "many" positive instances (i.e. frames), while each negative video contains few or no positive instances. They show that LLP outperforms baseline methods (mi/MI-SVM [START_REF] B I B L I O G R A P H Y Andrews | Support Vector Machines for Multiple-Instance Learning[END_REF]), especially by its capacity to relax the NINB assumption.

Other approaches depart from the NINB assumption by tracking the negative evidence of a class with regions [START_REF] Azizpour | Spotlight the Negatives: A Generalized Discriminative Latent Model[END_REF][START_REF] Parizi | Automatic discovery and optimization of parts for image classification[END_REF]. The main idea is to learn mutual exclusion constraints, e.g. model scene subcategories where the positive object class is unlikely to be found, or to capture specific parts, which potentially indicate the presence of an object of a similar but distinct class. [START_REF] Azizpour | Spotlight the Negatives: A Generalized Discriminative Latent Model[END_REF] proposes a generalization of LSVM by including negative latent variables. In [START_REF] Parizi | Automatic discovery and optimization of parts for image classification[END_REF], the authors introduce a WSL formulation specific to multi-class classification, where negative evidence is explicitly encoded by augmenting the model parameters to represent the positive/negative contribution of a part to a class.

Weakly Supervised Learning with Structured Output

In this section, we present WSL models for structured output that extend the WSL models of Subsection 2.2.1 to more general outputs, e.g. multi-class labels, ranking matrices, segmentation masks etc.

Structured Prediction

In structured output prediction, the goal is to predict a set of interdependent output variables y ∈ Y for a given input variable x ∈ X . To simplify the notations, we assume that all inputs have the same output domain Y. In the case where the output domain is different for different examples, it depends on the input: Y (x). The output y = [y 1 , y 2 , . . . , y M ] is composed of M individual outputs, and Y is a discrete and finite output domain. The elements of Y are structured discrete objects such as sequences, trees, graphs, ranking matrices, bounding boxes, segmentation masks, etc. Figure 2.5 shows an example of semantic segmentation, where the goal is to predict the semantic label of each pixel. We aim at predicting for each pixel, whether that the label of a pixel is dependent on neighbor pixels. If we know that all of the neighbors of a particular pixel are labeled table, then the pixel itself is most likely also labeled table. The core problem in structured output prediction arises from the combinatorial explosion. For example on ADE20K dataset (Bolei [START_REF] Zhou | Semantic understanding of scenes through the ade20k dataset[END_REF], there are 150 classes and the average image size is about 600 × 800, therefore the number of possible segmentation masks is about 10 10 6 .

Original image

Semantic segmentation mask The color of a pixel represent its category. The data is taken from the ADE20K dataset (http://groups.csail.mit.edu/vision/datasets/ADE20K/).

The goal of structured output prediction is to learn a function f w : X → Y that maps an input x ∈ X to an output y ∈ Y. The common approach involves computing a scoring (or compatibility, or discriminant) function s w : X × Y → R for each output, and then selecting the output with the maximum score, as follows:

ŷ(x) = f w (x) = arg max y∈Y s w (x, y) (2.7) Variable Notation Space Train Test Input x X observed observed Output y Y observed unobserved Latent h H unobserved unobserved
Table 2.1.: Details of the notations used in this thesis. For image classification, x is the image, y is the label and h is a region of the image.

where ŷ(x) is the predicted label. To simplify the notation, we note the predicted label ŷ (without the dependency of the input x) in the rest of this manuscript. The scoring function s w measures the compatibility between the input x and any output y.

In many structured output applications (e.g. semantic segmentation), it is expensive to obtain a fully supervised training dataset. To address this problem, the WSL strategy proposes to label inputs with weak labels (e.g. image-level labels), and to model the missing annotations with latent variables. In the WSL setting, an input-output (x, y) pair depends on a set of unobserved latent variables h ∈ H. For example, the image is labeled with image-level labels indicating the presence/absence of a class, and the latent variable h models the segmentation mask. The notations are summarized in Table 2.1. We now present the Latent Structured SVM (LSSVM), and its connection with standard latent structured output models.

Latent Structured SVM (LSSVM)

The Latent Structured SVM (LSSVM) (C.-N. [START_REF] Yu | Learning Structural SVMs with Latent Variables[END_REF]) extends the Structured SVM (SSVM) framework [START_REF] Taskar | Max-Margin Markov Networks[END_REF][START_REF] Tsochantaridis | Large Margin Methods for Structured and Interdependent Output Variables[END_REF] to include latent variables.

Model The scoring function depends on a latent variable h ∈ H, which is used to capture unobserved structures present in the input-output (x, y) pair. The latent variables are observed neither at training nor at evaluation time. We define a joint feature map Ψ : X × Y × H → R d , which describes the relationship between the input, the output and the latent variable. Given an input x and output y, the LSSVM scoring function searches the "best" latent variable value to measure the compatibility between the input x and the output y. Formally, the LSSVM scoring function is given by

s w (x, y) = max h∈H w, Ψ(x, y, h) (2.8)
where w ∈ R d is a parameter vector. The form of the feature map allows to learn models for problems as diverse as multi-class image classification [START_REF] Bilen | Object Classification with Latent Window Parameters[END_REF], natural language parsing (C.-N. [START_REF] Yu | Learning Structural SVMs with Latent Variables[END_REF], motif finding in yeast DNA (C.-N. [START_REF] Yu | Learning Structural SVMs with Latent Variables[END_REF]), 3D scene understanding [START_REF] Schwing | Efficient Structured Prediction with Latent Variables for General Graphical Models[END_REF]) and semantic image segmentation (J. Xu et al. 2014).

The maximization operation of Equation 2.7 is known as the prediction (or inference) problem and requires to maximize over both output and latent variable. If the sets Y and H have low cardinalities, we can use an exhaustive search. When the cardinalities of Y and H are large, exhaustive search is impractical. We need to use "smart" inference procedures: graph cuts [START_REF] Szummer | Learning CRFs using graph cuts[END_REF], belief propagation [START_REF] Schwing | Distributed Message Passing for Large Scale Graphical Models[END_REF], etc.

Learning In LSSVM (C.-N. [START_REF] Yu | Learning Structural SVMs with Latent Variables[END_REF], the optimization is defined as

min w 1 2 w 2 + C N N ∑ i=1 ∆(y i , f w (x i )) (2.9)
where C is the trade-off parameter and ∆ : Y × Y → R + is the loss function that penalizes mismatches between the ground truth output label y and a predicted label y. The form of the loss function depends on the nature of the problem. We assume the following properties of a loss function:

1. Non-negativity: ∆(y , y) ≥ 0 ∀y ∈ Y 2.
Zero for the ground-truth: ∆(y , y ) = 0 3. Upper bounded for every given target value, i.e. max y∈Y ∆(y , y) exists.

The loss function judges whether the prediction made for a training input is good, or similar enough to the ground truth output. However, the loss function ∆ is typically not convex nor continuous and piecewise constant w.r.t w, so optimizing it can be computationally expensive. To overcome this problem, the LSSVM replaces the loss function ∆ with a surrogate loss L. Formally, learning a LSSVM involves solving the following optimization problem min

w 1 2 w 2 + C N N ∑ i=1 L(x i , y i ) (2.10) with L(x i , y i ) = max (y,h)∈Y ×H [∆(y i , y) + w, Ψ(x i , y, h) ] -max h ∈H w, Ψ(x i , y i , h ) (2.11)
Intuitively, the above problem introduces a margin between the score of the ground-truth output together with the best value of the latent variable and any other pair of output and latent variables

max h∈H w, Ψ(x, y , h) ≥ ∆(y , y) + max h∈H w, Ψ(x, y, h) ∀y ∈ Y (2.12)
The model is trained such that it maximizes the margin between the ground-truth and any other output. The desired margin is proportional to the loss between the ground-truth and the corresponding output.

Optimization The LSSVM optimization problem is not a convex optimization problem, because of the max operation in a term with negative sign within Equation 2.11. However, (C.-N. [START_REF] Yu | Learning Structural SVMs with Latent Variables[END_REF] shows that the objective function (Equation 2.10) can be decomposed into a concave and convex function and efficiently be solved by the Concave-Convex Procedure (CCCP) [START_REF] Yuille | The concave-convex procedure[END_REF]. The CCCP is a simple iterative procedure that guarantees to converge to a local minimum or stationary point of the objective. The CCCP Algorithm 2.1 CCCP algorithm for learning LSSVM

Input: Initial model w, training dataset D = {(x i , y i )} N i=1 1: repeat 2: Update h i = arg max h∈H w, Ψ(x i , y i , h) ∀i ∈ {1, . . . , N} 3:
Update w by fixing the latent variables of the concave part min 2015). These solvers require to solve the Loss-Augmented Inference (LAI) problem, which is a maximization of the sum of the score of the output and the loss function arg max

w 1 2 w 2 + C N N ∑ i=1 max (y,h)∈Y ×H [∆(y i , y) + w, Ψ(x i , y, h) ] -w, Ψ(x i , y i , h i ) (2.
(y,h)∈Y ×H ∆(y , y) + w, Ψ(x, y, h) (2.13)
Intuitively, the LAI finds the most violated constraint. Solving efficiently the LAI problem is crucial to learn a SSVM, because it is the most time-consuming step.

Note that we can still use CCCP with an arbitrary function f , by using the generic Difference of Convex functions (DC) decomposition proposed in [START_REF] Yuille | The concave-convex procedure[END_REF] (Theorem 1). Given a convex function g, there exists a positive constant λ such that f vex (w) = f (w) + λg(w) is convex, and f cave (w) = -λg(w) is concave. So we can write an arbitrary function f as a difference of convex functions:

f (w) = f vex (w) + f cave (w) = f (w) + λg(w) -λg(w). This property is used in Subsection 4.4.1.1.

Connection with Latent Structured Output Models

As presented in the introduction, the pooling over latent variables is a key issue for WSL models. We have previously presented the LSSVM model, which uses a max operator (or pooling) over both output and latent variables during training. A drawback of max pooling is that is not robust to the inherent uncertainty on the variables, because it uses only the information of the maximum values. We now present some models with alternative pooling functions for both output and latent variables during training.

A similar model to LSSVM is the Marginal Structured SVM (MSSVM) [START_REF] Ping | Marginal Structured SVM with Hidden Variables[END_REF], which proposes to take into account the uncertainty on the latent variables by marginalizing them. But marginalizing over the latent variables usually requires more computation (y,h) . The temperature parameter enables to smooth between max ( → 0) and average ( → +∞) pooling. The conditional probability of output y and latent variable h given an input x can be defined as follows:

h → 0 + (max h ) h = 1 (log ∑ h exp) y → 0 + (max y ) LSSVM MSSVM y = h ∈ (0, 1) -framework y = 1 (log ∑ y exp) MLLR HCRF
P(y, h|x) = exp w,Ψ(x,y,h) ∑ y ∈Y,h ∈H exp w,Ψ(x,y ,h ) (2.15)
To compare the different methods, [START_REF] Ping | Marginal Structured SVM with Hidden Variables[END_REF]) introduces a unified framework. The general objective function is

1 2 w 2 + C N N ∑ i=1 y log ∑ y∈Y exp   ∆(y * i , y) + h log ∑ h∈H exp w,Ψ(x i ,y,h) h y   - C N N ∑ i=1 h log ∑ h∈H exp w, Ψ(x i , y * i , h) h (2.16)
where y and h are temperature parameters that control how much uncertainty we want to account for in y and h, respectively. The Table 2.2 summarizes the different models w.r.t y and h . We can note that both LSSVM and MLLR maximize over the latent variables, whereas both MSSVM and HCRF marginalize over the latent variables. -framework is a more general model, where HCRF and LSSVM are special cases.

Given a posterior distribution P(y, h|x) (Equation 2.15) and a loss function ∆, an open question is what is the optimal way to predict output and latent variables for a given input variable x? From a theoretical point of view, if the true posterior distribution is known, marginalizing over variables is the optimal predictor according to Bayesian decision theory [START_REF] Pletscher | Entropy and Margin Maximization for Structured Output Learning[END_REF], but maximizing over variables is also optimal for classification losses (e.g. zero-one loss). However, the optimality may not guaranteed because the true posterior is unknown in practice -it is estimated from labeled training data. Note that this problem of feature selection is a common and open question in machine learning. For example, if we consider supervised learning in the presence of many irrelevant features, a 1 regularization is often used to perform feature selection.

Weakly Supervised Learning of Deep ConvNets

Image Classification Datasets

In this section, we present standard image classification datasets used in this thesis. We evaluate our models in very different recognition contexts:

• Object recognition. The PASCAL VOC 2007 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2007[END_REF]) and PASCAL VOC 2012 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2012[END_REF] The multi-class datasets (i.e. one single class per image) are evaluated with multi-class accuracy, and the multi-label datasets (i.e. several classes per image) are evaluated with Mean Average Precision (MAP). For all datasets except MS COCO and PASCAL VOC 2012 Action, the performances are evaluated following the standard protocol. On MS COCO dataset, we follow the protocol in [START_REF] Oquab | Is object localization for free? -Weakly-supervised learning with convolutional neural networks[END_REF]. On PASCAL VOC 2012 Action, we use the same classification protocol than PASCAL VOC 2007 object classification, with evaluation on the val set. Table 2.3 summarizes dataset information.

Summary & Discussion

In Section 2.1, we have presented two approaches to compute visual representations for image classification: handcrafted (BoW) and learned (ConvNet) representations. Since few years, the ConvNets have become the state-of-the-art models for visual representation.

A key success of the ConvNets is that the learned representations on ImageNet are both discriminative and generic, so they can be efficiently transfered to other datasets (Subsection 2.1.2.4). They have also been successfully applied on other standard computer vision applications such as object detection, semantic segmentation, etc. Despite their The most popular approach for WSL in computer vision is Multiple-Instance Learning (MIL) (Subsection 2.2.1.1). MIL is a binary classification problem where a class label is assigned only to a bag of instances, indicating the presence/absence of positive instances. The standard MIL assumption is: a bag is positive if it contains at least one positive instance, and negative if it contains only negative instances. But, several methods show that MIL assumptions are not adapted for real data applications, and propose to relax the assumption that all instances in negative bags are negatives (Subsection 2.2.1.2). In Chapter 3, we introduce a new model SyMIL, which departs from standard negative instances in negative bags assumption and models positive and negative bags in a symmetric manner. Another important difference with existing approaches is that SyMIL model seeks discriminative instances in both positive and negative bags, whereas MIL models and their extensions seek discriminative instances in positive bags only.

Unfortunately, MIL is limited to binary labels. To deal with more complex outputs, a solution is to use the WSL models for structured output prediction. In Subsection 2.2.2.2, we present Latent Structured SVM (LSSVM), which generalizes Structured SVM (SSVM) by incorporating latent variables. As MIL models, LSSVM uses a max pooling over latent variables to perform prediction, but this pooling is not robust to the inherent uncertainty on the latent variable. As detailed in Subsection 2.2.2.3, several methods propose to take into account the uncertainty of the latent variables, by marginalizing. But, marginalizing over latent variables is usually slower than maximizing, and does not allow to explicitly select relevant regions. In Chapter 4, we introduce a new pooling strategy based on pairs of latent variables, which takes into account the uncertainty. While SyMIL seeks discriminative instances for positive and negative classes, the new prediction selects a pair of latent variables which provides positive and negative evidence for a given output. Contrary to standard pooling functions, this pooling function explicitly models negative evidence, e.g. a cow detector should strongly penalize the prediction of the bedroom class. As shown in Subsection 2.2.1.2 for MIL models, tracking the negative evidence of a class is important to have accurate prediction. Based on this pooling, we propose a new structured output latent variable model, called Minimum mAximum lateNt sTRucturAl SVM (MANTRA), which extends SyMIL to structured outputs.

Finally, we present deep ConvNet architectures for WSL with image-level labels. As Section 2.3 shows, the key issue is how to pool the regions to have a score per class. Most of the methods use a max, average or soft-max pooling. An analysis of these pooling functions is done in Section 6.5. In Chapter 5, we propose the WELDON pooling, which extends MANTRA to multiple regions to be more robust. We design a fully convolutional network architecture which enables fast region feature computation by convolutional sharing. In Chapter 6, we propose a new pooling function which extends WELDON pooling by incorporating a trade-off parameter to weight the positive and negative evidence terms. To enrich the model, we also introduce a class-wise pooling to learn several modalities per class. 3.1 Introduction D esigning powerful models able to handle weakly labeled data is a crucial problem in machine learning. This issue has been extensively studied during the last 20 years in several contexts: drug activity recognition, text classification, content-based image retrieval, etc. We presented leading techniques to model this problem as a Multiple-Instance Learning (MIL) problem in Subsection 2.2.1. The main MIL assumption is related to the relationship between bag and instance labels: a bag is positive if it contains at least one positive instance, and negative if it contains only negative instances. The standard MIL prediction used the instance with the maximum score to classify the bag. However, the Negative Instances in Negative Bags (NINB) assumption seems to be too restrictive for some applications (Subsection 2.2.1.2). To address this problem, several methods propose to relax the NINB assumption: a large portion of instances in a positive bag should be positive, whereas few instances in the negative bags may be positive.

In the same spirit, we propose SyMIL model, which models positive and negative bags in a symmetric manner. The main novelty of the SyMIL model is the introduction of an additional latent variable, to seek discriminative instances of the negative class (Subsection 3.2.1). To train the model, we propose a learning formulation (Subsection 3.2.2), and we show that this optimization problem can be cast as a Difference of Convex functions (DC), and optimized using the Concave-Convex Procedure (CCCP) (Section 3.3). In Subsection 3.4.1, we validate the intuition of SyMIL on toy datasets composed of synthetic or real data. Finally we evaluate SyMIL on standard MIL datasets (Subsection 3.4.2), and weakly supervised object detection datasets (Subsection 3.4.3).

SyMIL Model

We consider the problem of learning with weak supervision in a binary classification context. Training data are composed of N labeled bags D = {(x 1 , y 1 ), . . . , (x N , y N )} ∈ (X × Y ) N with binary labels (Y = {-1, +1}). Let us denote the set of positive bags as P = {(x i , y i ), y i = +1}, N + = |P |, and the set of negative bags as N = {(x i , y i ), andΦ(x, h) is the vectorial representation of the h-th instance.

y i = -1}, N -= |N |. Each bag x = {x h } h∈H is itself a set of |H| instances,

Prediction Function

Given an unlabeled bag x, we want to design a discriminant function s w : X → R, parametrized by w, such that f w (x) = sign [s w (x)] gives predicted label of x: s w (x) > 0 classifies the example as positive, and negative otherwise. We define two latent variables:

h + = arg max h∈H w, Φ(x, h) h -= arg min h∈H w, Φ(x, h) (3.1)
where h + (resp. h -) is the maximum (resp. minimum) scoring latent value for the linear model w, Φ(x, h) . Using h + and h -, we propose the following scoring function:

s w (x) = w, Φ(x, h + ) if w, Φ(x, h + ) ≥ -w, Φ(x, h -) w, Φ(x, h -) otherwise (3.2)
We note that this prediction function can be written as

f w (x) = sign[ w, Φ(x, h + ) + Φ(x, h -) ] (3.3)
To predict the bag label, Equation 3.3 sum the score of the instance with the maximum score, and the score of the instance with the minimum score. We now present the intuition of our prediction function.

Model intuition & discussion. The main novelty of the SyMIL model is the introduction of the latent variable h -: The rationale of the function s w (x) in Equation 3.2 is to compare the score of the most '⊕-like' instance (i.e. w, Φ(x, h + ) ) to the score of the most ' -like' instance (i.e.w, Φ(x, h -) ). h + (resp. h -) represents the most discriminative latent value for class ⊕ (resp. ). During training, we aim at using h + (resp. h -) for positive (resp. negative) bags, and so learning the most discriminative model. The SyMIL model is connected to the Learning with Label Proportion (LLP) model presented in Subsection 2.2.1.2. From the LLP perspective, SyMIL corresponds to a symmetric prior for the label proportion: for a positive bag (x, +1) (resp. negative bag (x, -1)), the proportion of positive (resp. negative) instances is p ⊕ (x, +1) ≥ 1 |H| (resp. p (x, -1) ≥ 1 |H| ). This departs from state-of-the-art SVM-like MIL algorithms, e.g. mi/MI-SVM [START_REF] B I B L I O G R A P H Y Andrews | Support Vector Machines for Multiple-Instance Learning[END_REF] and LSVM [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF], where the prediction function takes the form s w (x) = max h w, Φ(x, h) , corresponding to p ⊕ (x, +1) ≥ 1 |H| but p (x, -1) = 1. In this asymmetric modeling, ⊕ instances represent patterns that are discriminative for the ⊕ class, whereas instances are implicitly regarded as background (i.e. everything different from ⊕ instances in the feature space). In contrast, SyMIL assumes that the negative class presents a structure from which discriminative instances can be extracted. This is particularly relevant when the negative class is composed of examples from other categories, as in a multi-class context.

An illustrative comparison between symmetric and asymmetric MIL modeling is provided in Figure 3.1, for an image classification task. Here, bags represent images, and instances are rectangular image regions, in a simple two-class case (bison vs lama). Basically, asymmetric models tend to learn a function discriminating bison patches from the most difficult patches in negative images, i.e. background patches. In contrast, the symmetric SyMIL model seeks regions that are statistically discriminant for both positive and negative images (hopefully bison and lama patches), i.e. the instance the most distant from the hyperplane. SyMIL model tends to ignore background regions, i.e. those shared between ⊕ and images. This more semantic instance selection, and its translation to an improved predictive accuracy, is extensively studied in the experiments (section Section 3.4).

Learning

For learning, we define three constraints:

1. The first constraint ∀i ∈ P w, Φ(x i , h + i ) ≥ 1 (3.4)
enforces that the bag x i ∈ P is properly classified in the class ⊕, using the latent value h + i , with a safety margin of 1. This is satisfied for the positive bag in Figure 3.2.

2. The second constraint

∀i ∈ N w, Φ(x i , h - i ) ≤ -1 (3.5)
enforces that the bag x i ∈ N is properly classified in the class , using the latent value h - i , with a safety margin of 1. This is satisfied for the negative bag in Figure 3.2.

3. The third constraint ∀i ∈ D y i w, Φ(x i , h + i ) + Φ(x i , h - i ) ≥ 1 (3.6)
enforces that each positive (resp. negative) bag is represented by

h + i (resp. h - i ). For example, for y i = 1, it translates into w, Φ(x i , h + i ) ≥ -w, Φ(x i , h - i ) + 1, so that h + i is preferred over h - i to represent
x i with a safety margin of 1, and

s w (x i ) = w, Φ(x i , h + i ) . In Figure 3.2, this constraint is satisfied for the positive bag since ∆ = w, Φ(x i , h + i ) + Φ(x i , h - i ) ≥ 1.
In a similar fashion, this constraint is satisfied in Figure 3.2 for the negative bag with ∆ ≤ -1.

. ∆ = w, Φ(x, h + ) + Φ(x, h -) .
To optimize w over all the constraints, the following primal regularized loss P (w) is minimized:

P (w) = 1 2 w 2 + CL(w, D) (3.7) L(w, D) = 1 N N N + ∑ i∈P 1 -max h∈H w, Φ(x i , h) + + N N -∑ i∈N 1 + min h∈H w, Φ(x i , h) + + λ ∑ i∈D 1 -y i max h∈H w, Φ(x i , h) + min h∈H w, Φ(x i , h) + (3.8)
where C is a hyper-parameter that balances the regularization penalty and the empirical loss. P (w) contains the standard max margin regularization term and a data-dependent term L(w, D) penalizing the violation of the constraints using a hinge loss function [b] + = max(0, b). Note that it is easy to verify that the loss function L(w, D) in Equation 3.7 defined over the three constraints is a surrogate of the 0/1 loss on the prediction function f w .

Our prediction function

f w (x) = sign[ w, Φ(x, h + ) + Φ(x, h -)
] may be seen as an instantiation of the LSSVM prediction function (Equation 2.7). Indeed, with Y = {-1, 1} and Ψ(x, y, h) = y • Φ(x, h), we have f w (x) = arg max y∈Y max h∈H w, Ψ(x, y, h) . Interestingly, our prediction function f w is actually the natural instantiation of LSSVM to the binary classification case, which is not the case for competitive algorithms, e.g. mi/MI-SVM or LSVM. However, regarding learning formulation, P (w) in Equation 3.7 differs from the LSSVM objective with the previous instantiation of f w , which would correspond to only incorporating the third constraint (Equation 3.6). We add the constraints 1 (Equation 3.4) & 2 (Equation 3.5), because they correspond to the ultimate goal of the weakly supervised classifier: properly classifying (beyond the margin) training bags. We analyze the impact of these constraints in Subsection 3.4.2.

Theoretical Analysis We provide a bound of the average Rademacher complexity (R N ) of SyMIL model. We note F the hypothesis class for instances and F the hypothesis class for bags and we assume that the instances are in the hyper-sphere of radius B. To bound the average Rademacher complexity, we use the Theorem 20 of [START_REF] Sabato | Multi-Instance Learning with Any Hypothesis Class[END_REF]. The bound in the general case is:

R N ( F , D) ≤ 4 + 10 log(4ea 2 1 a 2 2 B 2 rN 2 )(A + a 1 a 2 β+1 K ln β+1 (16a 2 1 a 2 2 N)) √ N (3.9)
where r is the average bag size, N is the number of training examples, a 1 (resp. a 2 ) is the Lipschitz constant of bag-labeling (resp. loss) function, and A is a constant. The constant K and β must satisfy an inequality which depends on the worst-case Rademacher complexity over instances: R

sup N (F ) ≤ K ln β (N) √ N
. SyMIL learns a classification function in the instance space, so that the worst-case Rademacher complexity over instances is the same than SVM, i.e. R sup [START_REF] Bartlett | Rademacher and Gaussian Complexities: Risk Bounds and Structural Results[END_REF])), corresponding to β = 0 and K = W. Note that this bound is the same for LSVM, since both models use the same classification model over instances.

N (F ) ≤ W √ N 1 (proof in
As mentioned when drawing the connection with LSSVM, SyMIL prediction function in Equation 3.2 is equivalent to

f w (x) = sign[ w, Φ(x, h + ) + Φ(x, h -) ].
Therefore, the SyMIL bag-labeling function is 2-Lipschitz with respect to the infinity norm, because max and min functions are 1-Lipschitz with respect to the infinity norm. The loss function in Equation 3.7 is (1 + 2λ)-Lipschitz. Therefore, by substituting a 1 , a 2 , β and K values, we get following bound of the average Rademacher complexity:

R N ( F , D) ≤ 4 + 10 log(16eB 2 rN 2 (1 + 2λ) 2 )(A + 2(1 + 2λ)W ln(64(1 + 2λ) 2 N)) √ N (3.10)
The resulting bound indicates that there is a poly-logarithmic dependence of the sample complexity on the average bag size. By comparing SyMIL bound with the LSVM one provided by [START_REF] Sabato | Multi-Instance Learning with Any Hypothesis Class[END_REF], both bounds are similar and have the same order of magnitude2 . Despite selecting the maximum or minimum instance, which introduces a non-linearity to the hypothesis class, this bound enables a control of the model complexity.

We can note that SyMIL and LSSVM bounds have the same asymptotic behavior in ln(N) √ N .

Solving the Optimization Problem

Like competitive MIL algorithms (mi-SVM, MI-SVM, LSVM), the objective function P (w) (Equation 3.7) is not a convex function of w. In this section, we introduce our own solver to optimize P (w).

Difference of Convex Functions

First, we show that primal regularized loss (Equation 3.7) can be written as P (w) = u(w)v(w), where u and v are convex functions. Rewriting P (w) as a difference of convex functions is not straightforward given the form of Equation 3.7. For this purpose, we use the property max(0, ab) = max(a, b)b where a, b are convex functions. We also use the properties that the maximum of a linear functions is a convex function, and the minimum of a linear functions is a concave function. Next, we show that each hinge loss can be rewritten as a difference of convex functions. It is not straight-forward because each loss is neither a concave nor a convex function. For example, the first loss is the maximum of a concave function and a constant function, so it is neither a concave nor a convex function. But it can be rewritten as a difference of convex function with a = 0 and b

= -(1 -max h∈H w, Φ(x i , h) ): max(0, 1 -max h∈H w, Φ(x i , h) concave ) = max(0, max h∈H w, Φ(x i , h) -1) convex -(max h∈H w, Φ(x i , h) -1) convex (3.11)
Similarly, we can rewrite the global optimization problem P (w) as a difference of convex functions: P (w) = u(w)v(w) where:

u(w) = 1 2 w 2 + C N ∑ i∈P N N + max 0, max h∈H w, Φ(x i , h) -1 (3.12) + λ max 1 -min h∈H w, Φ(x i , h) , max h∈H w, Φ(x i , h) + ∑ i∈N N N -max 0, -min h∈H w, Φ(x i , h) -1 + λ max 1 + max h∈H w, Φ(x i , h) , -min h∈H w, Φ(x i , h) v(w) = C N ∑ i∈P N N + + λ max h∈H w, Φ(x i , h) - N N + (3.13) + ∑ i∈N - N N -+ λ min h∈H w, Φ(x i , h) + N N -
u and v are convex on w as a sum of convex functions.

Optimization

Once we exhibit the decomposition in difference of convex functions, we solve the resulting difference of convex functions using Concave-Convex Procedure (CCCP) [START_REF] Yuille | The concave-convex procedure[END_REF]. In addition to the CCCP convergence properties [START_REF] Sriperumbudur | On the Convergence of the Concave-Convex Procedure[END_REF] Linearize the concave part -v at the current solution w t / α t 6: until stopping criteria reach 7: return w t /α t minima. The overall scheme of our CCCP-based optimization is presented in Algorithm 3.1:

we alternate between linearizing the concave part (-v) at the current solution (Line 5) and solving the resulting convexified problem (Line 3). We now detail how the problem is solved in the primal and the dual.

Primal

The overall algorithm to train SyMIL with CCCP in the primal is given in Algorithm 3.2.

CCCP is an iterative algorithm that alternates between linearizing the concave part (-v) at the current solution w t (Line 5 of Algorithm 3.2) and solving the resulting convex problem (Line 3 of Algorithm 3.2). The linearization of the concave part -v(w) consists in upper bounding it by its tangent hyperplane: -v(w) ≤w, ∇ w v(w t ) , with:

∇ w v(w t ) = ∑ i∈P ( N N + + λ)Φ(x i , h + i,t ) -∑ i∈N ( N N -+ λ)Φ(x i , h - i,
P CCCP t (w) = u(w) -w, ∇ w v(w t ) (3.16) = u(w) - C N ∑ i∈P N N + + λ w, Φ(x i , h + i,t ) -∑ i∈N N N -+ λ w, Φ(x i , h - i,t )
At iteration t, to solve the convexified optimization problem min w P CCCP t (w) in the primal, we use a SGD strategy (Léon Bottou 2010) that proves to be simple and achieves fast convergence. Although we could use more efficient techniques, such as Stochastic Average Gradient (SAG) (Le [START_REF] Roux | A Stochastic Gradient Method with an Exponential Convergence Rate for Strongly-Convex Optimization with Finite Training Sets[END_REF], we find SGD sufficient in our experiments (Section 3.4). The gradient computation is given in Equation 3.17.

∇ w P CCCP t (w) = w + C N (D + E -( N N + + λ)Φ(x i , h + i,t )) if y i = +1 w + C N (F + G + ( N N -+ λ)Φ(x i , h - i,t )) otherwise (3.17)
Algorithm 3.2 for training SyMIL with CCCP (Primal)

Input: training set {(x i , y i )} i=1,...,N 1: Set t = 0, randomly initialize h + i,0 , h - i,0 and
g 0 = C N ∑ i∈P N N + + λ Φ(x i , h + i,0 ) -∑ i∈N N N -+ λ Φ(x i , h - i,0 ) (3.22) 2: repeat 3: Solve w t+1 = arg min w [u(w) -w, g t ] 4: t ← t + 1 5: Compute g t = ∇ w v(w t ) 6: until [u(w t ) -v(w t )] -[u(w t-1 ) -v(w t-1 )] < ε 7: return w t D = N N + Φ(x i , h + i ) if w, Φ(x i , h + i ) -1 > 0 0 otherwise (3.18) E = -λΦ(x i , h - i ) if 1 -w, Φ(x i , h - i ) > w, Φ(x i , h + i ) λΦ(x i , h + i ) otherwise (3.19) F = -N N -Φ(x i , h - i ) if -w, Φ(x i , h - i ) -1 > 0 0 otherwise (3.20) G = λΦ(x i , h + i ) if 1 + w, Φ(x i , h + i ) > -w, Φ(x i , h - i ) -λΦ(x i , h - i ) otherwise (3.21)

Dual

For many applications, nonlinear models are required to achieve good performances. We propose here a kernelized version of our SyMIL scheme. First, we detail the linearization of the concave part (Line 5 in Algorithm 3.1) in the dual, and then the solving of the convexified problem with cutting-plane.

Linearizing the concave part. To linearize the concave part at iteration t + 1, we have to fix the latent variables. For a bag x j , with current solution α (t) , the inference of the new latent variable value is:

h + j,t+1 = arg max h∈H ∑ k α (t) k 1 N ∑ i∈D (g cave (x i , h + i,t , h - i,t ) -g vex (x i , h + i , h - i )), Φ(x j , h) (3.23) h - j,t+1 = arg min h∈H ∑ k α (t) k 1 N ∑ i∈D (g cave (x i , h + i,t , h - i,t ) -g vex (x i , h + i , h - i )), Φ(x j , h) (3.24)
where the gradient of the convex and concave terms are:

g cave (x i , h + i,t , h - i,t ) = ( n n + + λ)Φ(x i , h + i,t ) if i ∈ P ( n n -+ λ)Φ(x i , h - i,t ) if i ∈ N (3.25)
Algorithm 3.3 Cutting plane algorithm with 1-slack formulation at iteration t

Input: training set {(x i , y i )} i=1,...,n , {(h + i,t , h - i,t )} i=1,...,n , precision ε 1: Set T = 0, c ← 0, H ← 0 2: repeat 3: H ← (H ij ) 1≤i,j≤T where H ij = g T (i) g (j) 4: α ← arg max α α T c -α T Hα s.t. 0 ≤ 1 T α ≤ C 5: ξ ← 1 C (α T c -α T Hα) 6:
T ← T + 1 7:

for i = 1, . . . , N do 8:

h + i ← arg max h∈H ∑ T-1 i=1 α i g (i) , Φ(x i , h) h - i ← arg min h∈H ∑ T-1 i=1 α i g (i) , Φ(x i , h) 9:
end for 10:

g (T) ← 1 N ∑ i∈D g cave (x i , h + i,t , h - i,t ) -g vex (x i , h + i , h - i ) 11: c T ← 1 N ∑ i∈D vex(x i , h + i , h - i ) -g vex (x i , h + i , h - i ), ∑ T-1 i=1 α i g (i) 12: until ∑ T-1 i=1 α i g (i) , g (T) ≥ c T -ξ -ε 13: return α g vex (x i , h + i , h - i ) = D + E if i ∈ P F + G if i ∈ N (3.26)
D, E, F, G are defined in equations 3.18 -3.21. (h + i,t , h - i,t ) are the predicted latent variable for linearizing the concave part at iteration t.

Solving the convexified problem. A direct resolution of the convexified problem in the dual would be intractable, as for many other kernelized (latent) structured output problems. We adopt a cutting-plane strategy to train our SyMIL model, using the 1-slack formulation [START_REF] Joachims | Cutting-Plane Training of Structural SVMs[END_REF]. The learning algorithm is given in Algorithm 3.3. Cutting-plane training searches the optimal solution and the set of active constraints simultaneously in an iterative manner. This algorithm is guaranteed to converge to an approximate solution with a reasonable number of outer loops. Starting from an empty working set of constraints, in each iteration it solves the optimization problem (Line 4) with only the constraints of the working set. Then it finds the most violated constraint (Line 7-11) and adds it to the working set. vex(x i , h + i , h - i ) is the convex term for bag x i and the equation is given in Equation 3.27.

vex(x

i , h + i , h - i ) =            N N + max(0, w, Φ(x i , h + i ) -1) if i ∈ P +λ max(1 -w, Φ(x i , h - i ) , w, Φ(x i , h + i ) ) N N -max(0, -w, Φ(x i , h - i ) -1) if i ∈ N +λ max(1 + w, Φ(x i , h + i ) , -w, Φ(x i , h - i ) ) (3.27)
The algorithm stops once no constraint can be found that is violated by more than the desired precision ε (Line 12). In our implementation, we use a stopping criterion defined by a fix number of iterations. During each iteration, we use MOSEK3 to solve the quadratic problem with the given set of active constraints (Line 4).

Evaluation

This section describes experiments performed and provides both qualitative and quantitative analysis on SyMIL models. We first perform experiments on toy datasets composed of synthetic or real data, and then evaluate SyMIL on standard MIL datasets and on weakly supervised object detection datasets.

Toy Experiments

In this section, we perform toy experiments on synthetic and real (image and text) data to validate the intuition of our model.

Synthetic data

We first show that SyMIL better separates classes than LSVM on simple datasets where both classes have similar distributions. We design synthetic toy datasets where positive and negative bags are modeled in a symmetric manner: instances are generated from two different Gaussian distributions, with a parameter α controlling the distance between them (see Figure 3.

Real image data

We now validate our intuition on real data. We use Mammal dataset [START_REF] Heitz | Shape-Based Object Localization for Descriptive Classification[END_REF], which is a multi-class dataset containing 6 categories: bison, deer, elephant, giraffe, llama and rhino. We use the same protocol as in [START_REF] Miller | Max-Margin Min-Entropy Models[END_REF]): the latent space H is composed of constant-size rectangular regions (which is a reasonable assumption for this dataset), and Histogram of Oriented Gradients (HOG) descriptors [START_REF] Dalal | Histograms of Oriented Gradients for Human Detection[END_REF]) are used as features Φ(x, h) for each region h. To have a similar setting as in Figure 3.1, we use only the classes bison and llama. We report in Table 3.1 the classification results for bison vs llama (bison (resp. llama) is the positive (resp. negative) class) and llama vs bison (llama (resp. bison) is the positive (resp. negative) class). The performances are evaluated using a 10-fold cross-validation.

We note that our model has better results than LSVM. For bison vs llama experiment, SyMIL seeks discriminative regions for both bison and llama, while LSVM seeks discriminative regions only for bison. We note that reverse the positive and negative class gives different results for LSVM, because it use an asymmetric strategy, whereas our model gives the same results, because it use a symmetric strategy. We finally analyze our model on a dataset where the negative class is composed of several concepts. We perform experiments on a text dataset from Reuters21578 4 . We choose the category money as positive examples and ship, crude as negative. 100 documents from the 3 categories are randomly selected. Each document is a bag, and each paragraph is an instance. To represent each paragraph, we use tf-idf feature with vocabulary of size 18933. Performances are evaluated using a 10-times 5-fold cross-validation.

Results given in Table 3.2 a) show that SyMIL outperforms LSVM in terms of predictive accuracy (97.6% vs 96.3%). To analyze the instances selected by the two models, we compute the semantic similarity between the words in the selected instances and the related category, using Wu and Palmer (WP) similarity measure [START_REF] Palmer | Verb semantics for English-Chinese translation[END_REF]) on WordNet 5 . More precisely, the similarity is determined by computing the ratio of words that have a WP similarity with respect to the category larger than a threshold (set here to 0.2). For negative bags, we use the maximum similarity between ship or crude. In Table 3.2 b), we notice that LSVM and SyMIL perform similarly (74% vs 73 %) for positive bags, whereas SyMIL is much better than LSVM for negative bags (78% vs 67 %). This highlights the superiority of the symmetric modeling to select instances which are representative of the negative class. Finally, Table 3.2 c) shows an example of the 5 words that mostly contribute to the decision function. The top 5 selected words are generated as follows: for each selected instance (i.e. paragraph) we compute the top 5 words (i.e. dimensions in the instance space) that mostly contribute to the classification score (largest components of |w|), and average over all positive/negative bags. More precisely, for word k, we compute a histogram of contribution w k × Φ(x, h predict ) [k]. We can point out that SyMIL extracts words that are semantically in touch with the negative class, e.g. (oil, OPEC) for crude and (port, shipping) for ship. On the contrary, LSVM selected words are not always semantically meaningful for the negative class, and are even more related to the positive class (money).

Standard MIL Dataset Results

We demonstrate the efficiency of SyMIL on standard MIL datasets • Musk datasets: consists of descriptions of molecules using multiple low-energy conformations. Each conformation is represented by a 166-dimensional feature vector derived from surface properties.

• Image datasets: an image consists of a set of segments, each characterized by color, texture and shape descriptors. There are three different datasets ("elephant", "fox", "tiger"). In each case, the dataset has 100 positive and 100 negative example images. The latter have been randomly drawn from a pool of photos of other animals.

• Text datasets: starting from the publicly available TREC9 data set, each document is split into passages using overlapping windows of maximal 50 words each. Then, documents are annotated with MeSH terms (Medical Subject Headings), each defining a binary concept. The parametrization for our method is the following. Regarding hyper-parameters (Equation 3.7), C is fixed to a large value7 (10 4 ). λ is chosen by cross-validation on the training set, on the range {0.1, 0.2, 0.5, 1}. We evaluate our method with linear and Radial Basis Function (RBF) kernels (k(a, b) = exp(-γ ab 2 2 )). The scale parameter γ for RBF kernels is determined as the mean pairwise instance distance on the training set. Note that we could expect further improving performances by cross-validating it more carefully. For all methods, the initial latent variables are randomly selected. We follow

Method

Image Musk Text Avg. [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF]. From a modeling point of view, these approaches basically differ from ours by the way instances are selected in positive and negative bags during training. We re-implement the three methods in order to compare the methods on the same splits. For mi-SVM and MI-SVM, we use linear kernels, that were reported to achieve optimal performances 8 (Andrews et al. 2003). One can notice SyMIL with linear kernel significantly outperforms mi-SVM, MI-SVM and LSVM: on average in the three types of data, there is a gain of about 4 pt over the best baseline. We perform paired t-test to assess the statistical significance of the difference in each dataset. It turns out that SyMIL is statistically better than its competitors with a risk of 1% for all image and molecule datasets, and for 5 of the 7 text datasets. These results clearly highlight the relevance of our model, i.e. the importance of seeking discriminative instances in both positive and negative bags.

Using non-linear kernels can further improve performances: about 1 pt increase in the image and molecule datasets. However, for the text datasets, the linear model outperforms RBF kernels. Note that this trend is conform to the results reported in GP-WDA [START_REF] Kim | Multiple Instance Learning via Gaussian Processes[END_REF]. We also evaluate the performance reached when using the LSSVM (Subsection 2.2.2.2) instantiation corresponding to our prediction function, i.e. Ψ(x, y, h) = y • Φ(x, h). As explained in Subsection 3.2.2, the SyMIL learning scheme is different from this LSSVM instantiation, which translates in ignoring constraints 1 (Equation 3.4) & 2 (Equation 3.5). We observe a performance drop between 1 and 3 pt depending on the dataset (Image-Molecule), and on the kernel type (linear vs RBF). For example, the superiority of our method is largely significant on Elephant (t-test validation with a risk of 5%). It confirms that enforcing constraints 1 & 2 is relevant and favorably impacts classification performances.

An absolute performance comparison with recent state-of-the-art works is provided in Table 3.4 b). On average on the three datasets, our method outperforms all reported results9 . Competitive approaches in these datasets include recent works such as MILEAGE (D. [START_REF] Zhang | MILEAGE: Multiple Instance LEArning with Global Embedding[END_REF], GP-WDA [START_REF] Kim | Multiple Instance Learning via Gaussian Processes[END_REF]) which solves the MIL problem using Gaussian Processes, eMIL [START_REF] Krummenacher | Ellipsoidal Multiple Instance Learning[END_REF] or MI-CRF [START_REF] Deselaers | A Conditional Random Field for Multiple-Instance Learning[END_REF] or MIGraph (Z.-H. [START_REF] Zhou | Multi-instance Learning by Treating Instances As non-I.I.D. Samples[END_REF]. Despite the complex models used by these strong competitors, SyMIL outperforms them in the image and text databases. Although our method remains very competitive on the Musk datasets, it is slightly outperformed by MIGraph. One explanation may be that MIL assumptions are better satisfied on this historical dataset. Note, however, that MIGraph performs poorly on the image dataset. To summarize, the excellent results for the three applications exhibit the capacity of our method to successfully handle various types of data. Note that the local information in SyMIL can be combined with a global bag feature, as done in MILEAGE (D. [START_REF] Zhang | MILEAGE: Multiple Instance LEArning with Global Embedding[END_REF] or MI-CRF.

Analysis of hyper-parameter λ

We also study the performances with respect to the parameter λ, which is an important hyper-parameter for SyMIL model. This hyperparameter adjusts the trade-off between constraints 1 & 2 and constraint 3 during training. A large λ is similar to LSSVM (see Subsection 3.2.2) because the constraints 1 & 2 are negligible with respect to the constraint 3. Figure 3.5 shows the results on Musk2 and Elephant datasets, for a λ on the range [0.01, 1000]. We observe that the best results are for a lambda around 1 on Musk2, and 0.1 on Elephant. The optimal λ changes for each dataset. Note that using a small λ leads to bad results because the model is not able to predict the relevant instance.

Weakly Supervised Object Detection

In weakly supervised object detection, the goal is to learn a model, which jointly classifies the image and localizes the object. Training data only have image-level labels indicating the presence/absence of each object category in an image. The exact object location in the image is unknown and is modeled as a latent variable h. We make experiments on two different datasets: Mammal dataset and PASCAL VOC 2007.

Classification results

Mammal dataset This dataset is presented in Subsection 3.4.1.2. To perform multi class classification, we use 1 vs All strategy. The performances are evaluated using a 10-fold cross-validation. We compare the proposed SyMIL RBF model to LSVM [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF]) and its recently kernelized version (W. [START_REF] Yang | Kernel Latent SVM for Visual Recognition[END_REF], using a RBF kernel.

In addition, we evaluate Max-Margin Min-Entropy (M3E) [START_REF] Miller | Max-Margin Min-Entropy Models[END_REF]) by using the code available online10 . The best performing M3E models use a small value of α, so we fix α = 5 for our experiments. We measure prediction performances by using accuracy, and Mean Average Precision (MAP) to be robust to the ⊕/ unbalance. The classification results are shown in Table 3.6. We compare SyMIL and LSVM. As observed in previous experiments, SyMIL outperforms LSVM. It confirms that seek discriminative instances for both positive and negative class is relevant, even on challenging dataset like PASCAL VOC 2007.

Method

Detection results

We analyze the predicted regions for weakly supervised object detection. We report localization performances to quantitatively evaluate the quality of the predicted latent values. We use the standard detection metric [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2007[END_REF], measuring the overlap between the predicted and ground truth bounding boxes. We consider that a prediction is correct if the overlap is larger than 0.5.

Table 3.7 summarizes the average performances for both detection metrics on Mammal dataset. SyMIL outperforms asymmetric approaches for both metrics. In addition, all improvements are statistically significant (risk 5%). Detection results are connected to prediction performances. They quantitatively validate the motivation of the method, i.e. the fact that SyMIL is better able than asymmetric MIL models to track the structure of the negative class. In this dataset, we show that SyMIL successfully localizes regions containing object of the five categories composing the negative class. Visualizations For VOC 2007, we normalize the overlap by the area of the predicted bounding box. Used the intersection over union score is not adapted, because we have only one size of box. If the ground truth bounding box is smaller than the size of the bounding boxes, it is not possible to have a good score even if the ground truth is in the predicted region. We observe similar results as on Mammal Dataset. SyMIL achieves better results for classification (+2,1%) and detection (+6% on training set) than LSVM (Table 3.6).

Conclusion

In this chapter, we introduced SyMIL, a new model for learning from weakly labeled data. Following Learning with Label Proportion (LLP) ideas, SyMIL models positive and negative bags in a symmetric manner, using a pair of latent variables. SyMIL is trained by defining a regularized large margin objective function, with specific dedicated constraints. We provided a primal solver based on Stochastic Gradient Descent (SGD) and a dual solver based on one-slack cutting-plane. In addition, we derived a generalization error bound based on the Rademacher complexity, which shows that our model has the same asymptotic behavior that standard MIL models.

Successful experimental results are reported on standard MIL and weakly supervised object detection datasets: SyMIL significantly outperforms competitive methods (mi-SVM, MI-SVM, LSVM), and gives very competitive performances compared to state-of-the-art works. The analysis of the SyMIL instance selection strategy on weakly supervised object detection and text classification tasks revealed the capacity of the symmetric modeling to track the structure of the negative class.

A limitation of SyMIL relies on the prediction function which selects a single instance, making the method sensitive to false alarm outliers. To improve the prediction, it could be interesting to combine SyMIL approach with LLP (see Appendix A) or to extend the prediction function to multiple instances, i.e. to select the k most positive (resp. negative) instances instead of the most positive (resp. negative) instance (Chapter 5). Another interesting strategy is to model interactions between bag instances as is done in MI-CRF or MIGraph. Another limitation of SyMIL is that bags are labeled with binary labels, while a lot of datasets are labeled with multi-class labels. To address this problem, a solution is to use WSL models for structured output prediction, e.g. LSSVM. In the next chapter, we present a new model which generalizes SyMIL to structured output prediction, e.g. multi-class, ranking, etc.

Introduction

D eep learning with ConvNets is becoming a key ingredient of visual recognition systems (Subsection 2.1.2). Internal ConvNet representations trained on large scale datasets currently provide state-of-the-art features for various tasks, e.g. image classification or object detection. To overcome the limited invariance capacity of ConvNets, bounding box annotations are often used. However, collecting full annotations for all images in a large dataset is an expensive task, and makes the development of Weakly Supervised Learning (WSL) models appealing (Section 1.2).

In Chapter 3, we introduced a max+min prediction function for WSL dedicated to binary classification. In this chapter, we introduce Minimum mAximum lateNt sTRucturAl SVM (MANTRA), a new WSL model for structured output that extends SyMIL to more general outputs (multi-class label, ranking). Our first contribution is the extension of the max+min prediction function to structured output (Section 4.2). We also show that the minimum latent variable explicitly models negative evidence, i.e. looks for "counter evidence" for the class. Our second contribution is that the MANTRA prediction function enables to efficiently tackle the important problem of learning to rank (Subsection 4.3.2), 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 because the AP does not decompose linearly in the examples. Finally, extensive experiments highlight the relevance of MANTRA for multi-class classification (Subsection 4.4.1) and ranking (Subsection 4.4.2).

MANTRA Model

We present here the proposed WSL model: Minimum mAximum lateNt sTRucturAl SVM (MANTRA). We follow the notations introduced in Subsection 2.2.2. 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. For example for multi-class image classification, x is the image, y is a multi-class label, h is a region of image x and Ψ(x, y, h) is the vectorial representation of region h of image x for label y. Our goal is to learn a prediction function f w , parametrized by w ∈ R d , to predict the output. During training, we assume that we are given a set of

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

Prediction Function

As mentioned earlier, 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) (4.1)
For an input/output pair (x i , y), the scoring of the model, s w (x i , y), sums h + i,y and h - i,y scores, as follows:

s w (x i , y) = w, Ψ(x i , y, h + i,y ) + w, Ψ(x i , y, h - i,y ) (4.2)
Finally, MANTRA prediction outputs ŷi = f w (x i ) which maximizes s w (x i , y) w.r.t. y:

ŷi = f w (x i ) = arg max y∈Y s w (x i , y) (4.3)
Connection with SyMIL If we consider the feature map Ψ(x, y, h) = y • Φ(x, h) and Y = {-1, +1}, the MANTRA prediction function is equivalent to SyMIL prediction function (Equation 3.2).

Intuition Let us consider a multi-class classification instantiation of MANTRA, where latent variables h correspond to part localizations. To highlight the importance of the pair (h + , h -), we show in Figure 4.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 substantially 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. Note that the vector of parameters w is common for both latent variables h + and h -. The same model learns which regions are discriminative for the class and which regions indicate the absence of the class. The minimum region h -can be seen as a regularizer on the latent space exploiting contextual information.

Learning Formulation

During training, we enforce the following constraints:

∀y = y i , s w (x i , y i ) ≥ ∆(y i , y) + s w (x i , y) (4.4)
Each constraint in Equation 4.4 requires the scoring value s w (x i , y i ) for the correct output y i to be larger than the scoring value s 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 Equation 4.4, let us notice that: • s 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,y i , which represent strong evidence for the presence of y i , while enforcing h - i,y i variables not having large negative scores. • s w (x i , y), i.e. the score for an incorrect output y = y i , 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 Equation 4.4 to be violated, we introduce the following loss function:

a) s l (h + ) = 1.8 ; s l (h -) = 0.1 b) s c (h + ) = 1.5 ; s c (h -) = -0.8
L w (x i , y i ) = max y∈Y [∆(y i , y) + s w (x i , y) -s w (x i , y i )] (4.5)
The loss function L w (x i , y i ) (Equation 4.5) is an upper bound of ∆(y i , ŷi ).

Proof. We show that the loss function L w (x i , y i ) (Equation 4.5) is an upper bound of ∆(y i , ŷi ), where x i is the input, y i is the ground truth, and ŷi = arg max y∈Y s w (x i , y) is the predicted output.

∆(y i , ŷi ) ≤ ∆(y i , ŷi ) + s w (x i , ŷi ) -s w (x i , y i ) ≥0 (4.6) ≤ max y∈Y ∆(y i , y) + s w (x i , y) -s w (x i , y i ) (4.7) ≤ L w (x i , y i ) (4.8)
This proves that L w (x i , y i ) is an upper bound of ∆(y i , ŷ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 L w (x i , y i ) (4.9)

Optimization

The problem in Equation 4.9 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 Equation 4.9 can thus be rewritten as follows:

min w,ξ 1 2 w 2 + Cξ s.t. ∀( ŷ1 , . . . , ŷN ) ∈ Y N (4.10) s.t. 1 N N ∑ i=1 ∆(y i , ŷi ) + s w (x i , ŷi ) -s w (x i , y i ) ≤ ξ
The key idea of the 1-slack formulation in Equation 4.10 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 SSVMs, 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 Equation 4.10. 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, under-estimating 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 (Do et al. 2012). Based on (Do et al. 2012), we derive a non-convex cutting plane algorithm to solve Equation 4.10. In particular, we use a method to detect and solve conflicts when adding a new cutting plane, as in (Do et al. 2012), in order to avoid over-estimating 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 4.1. Starting from an initial cutting plane (Line 1), each cutting plane iteration consists in solving the resulting Quadratic Program (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 Equation 4.10 (Line 5) is derived in Appendix B. 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 sub-gradient ∇ w L w (Line 13). The sub-gradient is:

∇ w L w (x i , y i ) = ∇ w s w (x i , ŷi ) -∇ w s w (x i , y i ) (4.11) where ∇ w s w (x i , y) = Ψ(x i , y, h + i,y ) + Ψ(x i , y, h - i,
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 // Compute new cutting plane and solve conflict 13:

g t ← 1 N ∑ N i=1 -∇ w L w (x i , y i ) 14: c t ← 1 N ∑ N i=1 ∆(y i , ŷi )
15:

(g t , c t ) ← SolveCon f lict(w, g t , c t )

16: until w, g t ≥ c tξε 17: return 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 (Equation 4.3), and loss-augmented inference (Equation 4.13):

ŷ = arg max y∈Y ∆(y i , y) + s w (x i , y) (4.13)
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)] (4.14)
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 loss-augmented inference are exhaustively solved.

AP Ranking Instantiation

Context The Average Precision (AP) metric is often used in information retrieval and many computer vision tasks, such as PASCAL challenges [START_REF] Everingham | The Pascal Visual Object Classes Challenge: A Retrospective[END_REF]. Optimizing ranking models with AP is challenging even in the fully supervised case. An elegant instantiation of SSVM 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. To optimize this surrogate, the key issue is how to solve the Loss-Augmented Inference (LAI) problem. [START_REF] Yue | A Support Vector Method for Optimizing Average Precision[END_REF] propose a greedy algorithm to find an optimal solution. Recently, [START_REF] Mohapatra | Efficient Optimization for Average Precision SVM[END_REF] proposes a more efficient method by taking in account the structure of the problem. Instead of optimizing a convex surrogate, [START_REF] Song | Training Deep Neural Networks via Direct Loss Minimization[END_REF] proposes a direct loss minimization to optimize AP.

In the WSL setting, optimizing AP is, however, a very challenging problem: for example, no algorithm exists for solving the loss-augmented inference problem with LSSVM (Subsection 2.2.2.2). In [START_REF] Behl | Optimizing Average Precision Using Weakly Supervised Data[END_REF], Latent AP-SVM (LAPSVM) is introduced, enabling 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. In this section, we propose a MANTRA AP ranking instantiation, which allows an efficient solving of both inference and loss-augmented inference problems.

Contrary to multi-class classification, for AP ranking there is one example that contains all the examples, i.e. x = {x i , i = 1, . . . , N}. This formalism can be explained by the fact that we need all the examples to evaluate the AP loss [START_REF] Yue | A Support Vector Method for Optimizing Average Precision[END_REF]. The indexes for the positive and negative samples are denoted by P and N respectively. In other words, if p ∈ P and n ∈ N then x p belongs to positive class and x n belongs to the negative class. The structured output is a ranking matrix y of size N × N providing an ordering of the training examples, such that:

• y ij = 1 if x i ≺ y x j i.e. x i is is ranked ahead of x j ; • y ij = -1 if x j ≺ y x i i.e.
x j is is ranked ahead of x i ;

• 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 if (i, j) ∈ P × N , y * ij = 0 if (i, j) ∈ P × P and y * ij = 0 if (i, j) ∈ N × N . We now present the joint feature map and the loss function.

Joint Feature Map The joint feature map Ψ(x, y, h) is defined as follows:

Ψ(x, y, h) = 1 |P ||N | ∑ p∈P ∑ n∈N y pn (Φ(x p , h p,n ) -Φ(x n , h n,p )) (4.15)
The latent space H corresponds to the set of latent variables for each pair of positivenegative examples:

h = {(h p,n , h n,p ) ∈ H p × H n , (p, n) ∈ P × N }, where H p (resp. H n ) is the set of locations in image x p (resp. x n ). Φ(x p , h p,n ) ∈ R d (resp. Φ(x n , h n,p
)) is thus a vectorial representation of image x p (resp.

x n ) at location h p,n (resp. h n,p ). Note that Ψ(x, y, h) in Equation 4.15 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.

We especially focus on AP, with ∆ AP (y , y) = 1 -AP(y , y), where AP(y , y) is the AP score [START_REF] Baeza-Yates | Modern Information Retrieval[END_REF]) between rankings y and y. Optimizing ∆ 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 (C.-N. [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 now show that inference and loss-augmented inference can be solved exactly and efficiently with MANTRA. Firstly, we show (Lemma 4.1) that in our ranking instantiation, s w (Equation 4.2) 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 4.1. ∀(x, y), s w (x, y) in Equation 4.2, for the ranking instantiation of Ψ given in Equation 4.15, rewrites as Θ(x, y):

Θ(x, y) = 1 |P ||N | ∑ p∈P ∑ n∈N y pn w, Φ + -(x p ) -w, Φ + -(x n ) (4.16)
where w,

Φ + -(x i ) = max h∈H i w, Φ(x i , h) + min h∈H i w, Φ(x i , h)
Proof. We prove that s w (x, y) can be re-written as a supervised feature map, where the score of each example x i is w, Φ + -(x i ) . Given an input x, and an output y and a weight vector w, we have:

s w (x, y) =max h∈H w, Ψ(x, y, h) + min h ∈H w, Ψ(x, y, h ) (4.17) =max h∈H 1 |P ||N | ∑ p∈P ∑ n∈N y pn ( w, Φ(x p , h p,n ) -w, Φ(x n , h n,p ) ) (4.18) + min h ∈H 1 |P ||N | ∑ p∈P ∑ n∈N y pn ( w, Φ(x p , h p,n ) -w, Φ(x n , h n,p ) ) = 1 |P ||N | ∑ p∈P ∑ n∈N max (h p ,h n )∈H p ×H n y pn ( w, Φ(x p , h p ) -w, Φ(x n , h n ) ) (4.19) + 1 |P ||N | ∑ p∈P ∑ n∈N min (h p ,h n )∈H p ×H n y pn ( w, Φ(x p , h p ) -w, Φ(x n , h n ) )
With the definition of the latent variable and the joint feature, the maximization (resp. minimization) over the latent variables can be decomposed for each term of the sum. So maximizing (resp. minimizing) the sum is equivalent to maximize (resp. minimize) each term of the sum independently, because the latent variable h can be decomposed for each term of the sum and each couple of latent variables (h p,n , h n,p ) is independent. Now, the two sums are grouped in a single sum:

1 |P ||N | ∑ p∈P ∑ n∈N max (h p ,h n )∈H p ×H n y pn ( w, Φ(x p , h p ) -w, Φ(x n , h n ) ) (4.20) + 1 |P ||N | ∑ p∈P ∑ n∈N min (h p ,h n )∈H p ×H n y pn ( w, Φ(x p , h p ) -w, Φ(x n , h n ) ) = 1 |P ||N | ∑ p∈P ∑ n∈N max (h p ,h n )∈H p ×H n y pn ( w, Φ(x p , h p ) -w, Φ(x n , h n ) ) (4.21) + min (h p ,h n )∈H p ×H n y pn ( w, Φ(x p , h p ) -w, Φ(x n , h n ) )
We define

Θ(x, y) = 1 |P ||N | ∑ x i ∈P ∑ x j ∈N max (h p ,h n )∈H p ×H n y ij ( w, Φ(x p , h p ) -w, Φ(x n , h n ) ) + min (h p ,h n )∈H p ×H n y ij ( w, Φ(x p , h p ) -w, Φ(x n , h n ) ) (4.22)
By construction, we have the equality A(x, y) = s w (x, y). Now, we show that the latent variables can be fixed independently to the ranking matrix y. For a couple of examples (x p , x n ), with p ∈ P, n ∈ N , we analyze the value of the latent variables h p , h n , h p , h n with respect to y pn . There are only two cases to analyze: y pn = 1 and y pn = -1.

If y pn = 1 max (h p ,h n )∈H p ×H n ( w, Φ(x p , h p ) -w, Φ(x n , h n ) ) (4.23) + min (h p ,h n )∈H p ×H n ( w, Φ(x p , h p ) -w, Φ(x n , h n ) ) = w, Φ(x p , h + p ) -w, Φ(x n , h - n ) + w, Φ(x p , h - p ) -w, Φ(x n , h + n ) (4.24) = w, Φ + -(x p ) -w, Φ + -(x n ) (4.25) where Φ + -(x i ) = Φ(x i , h + i ) + Φ(x i , h - i ) (4.26) h + i = arg max h∈H i w, Φ(x i , h) h - i = arg min h∈H i w, Φ(x i , h) (4.27) If y ij = -1 max (h p ,h n )∈H p ×H n -( w, Φ(x p , h p ) -w, Φ(x n , h n ) ) (4.28) + min (h p ,h n )∈H p ×H n -( w, Φ(x p , h p ) -w, Φ(x n , h n ) ) = max (h p ,h n )∈H p ×H n ( w, Φ(x n , h n ) -w, Φ(x p , h p ) ) (4.29) + min (h p ,h n )∈H p ×H n ( w, Φ(x n , h n ) -w, Φ(x p , h p ) ) = w, Φ(x n , h + n ) -w, Φ(x p , h - p ) + w, Φ(x n , h - n ) -w, Φ(x p , h + p ) (4.30) = -( w, Φ + -(x p ) -w, Φ + -(x n ) ) (4.

Experiments

In this section, we present an evaluation and analysis of MANTRA for multi-class classification and ranking tasks. In our implementation, we use MOSEK1 to solve the Quadratic Program (QP) at each cutting plane iteration (Line 5 of Algorithm Algorithm 4.1 for MANTRA). By default, the regularization parameter C is fixed to a large value, e.g. 10 5 . An analysis of this parameter is done in Subsection 4.4.2.

Multi-class Classification

In this section, we analyze our multi-class model (Subsection 4.3.1) on four datasets. We evaluate our multi-class model for four different visual recognition tasks: scene categorization (15 Scene), cluttered indoor scenes (MIT67), fine-grained recognition (PPMI) and complex event and activity images (UIUC-Sports). These datasets are presented in Section 2.4. We now present how the feature regions are extracted.

Features We extract region features for different bounding box scales: from 30% to 90% of the image size, with a step of 10%. The number of regions per image for each scale is given in Table 4.1. 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 (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 [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF]) (resp. Places (B. Zhou et al. 2014)).

MANTRA Analysis

In this section, we provide an analysis of our method. We first study the accuracy and training time with respect to the bounding box scale, because the bounding box scale is an important hyper-parameter of our model. Then, we compare MANTRA to the popular LSSVM (C.-N. [START_REF] Yu | Learning Structural SVMs with Latent Variables[END_REF]), and we show visual results.

Mono-scale results

We report MANTRA results with respect to the bounding box scale in Figure 4.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 4.3). [START_REF] Yuille | The concave-convex procedure[END_REF] to solve the non-convex optimization problem.

Time analysis

To further analyze the performance gain of MANTRA vs LSSVM, we isolate in Table 4.2 the impact of the new prediction function (Section 4.2) by training MANTRA with CCCP (MANTRA-C), and the Non-Convex Cutting-Plane (NCCP) optimization (Subsection 4.2.3), by training LSSVM with NCCP (LSSVM-N). CCCP leads to slightly better results for LSSVM, because the decomposition proposed by (C.-N. [START_REF] Yu | Learning Structural SVMs with Latent Variables[END_REF]) exploits the structure of the optimization problem. In contrast, MANTRA objective (Equation 4.9) does not directly rewrites as a Difference of Convex functions (DC). By using the generic DC decomposition detailed in Subsection 2.2.2.2, we can used CCCP for MANTRA: results in Table 4.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 results

In Figure 4. 4 (resp. Figure 4.5,Figure 4.6), we show visual results on UIUC-Sports (resp. MIT67 and 15 Scene) dataset. We show prediction maps and (h + , h -) regions, for different classifiers. For instance, when classifying a snowboard image (Figure 4.4, last row), the snowboard classifier learns that the most discriminative region is the region with the snowboard and the feet of the person. It also learns that all the other regions are relevant and assign a high score to all regions, including the h -region. The bocce classifier learns that the head of the person is quite discriminative, but it also learns that bocce is not practiced on the snow, and assign a very low score to the h - region, which focuses on the snow. Similarly, the h -region of croquet (resp. polo) classifier focuses on the snow, which supports the absence of croquet (resp. polo) class. For the correct class, the incorporation of h -prevents from having large negative values for any (random) window. The fourth row of Figure 4.4 shows the prediction of sailing and rowing categories for a sailing image. For each classifier, h + corresponds to discriminative parts, i.e. boat with sail and water. The h -region for the rowing classifier focuses on the sail of the boat with a very low score. It suggests that if a sail is found, the image is very unlikely to belong to the class rowing. Another example is the greenhouse image of MIT67 (second row of Figure 4.5), where both greenhouse and florist classifiers have high scores and focus on plants. For the greenhouse classifier, h -has a quite high score, so all regions are discriminative for it. This is in stark contrast to the florist classifier, for which h - focuses on the roof of the greenhouse, and has a very low score because this structure with walls and roof made of transparent material is never present in florist shop. The roof of the greenhouse is a clear evidence of the absence of the florist category. For classifiers of uncorrelated categories like laboratorywet, all regions have very low scores because the roof structure and the plant are never present in laboratory wet. In

Comparison with State-of-the-Art Methods

We now compare our model with state-of-the-art models. The mono-scale results (Subsection 4.4.1.1) suggest the idea of combining several scales, which are expected to convey complementary informations. To perform scale combination, we use an Object Bank (OB) (L.-J. [START_REF] Li | Object Bank: An Object-Level Image Representation for High-Level Visual Recognition[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]J. Sun et al. 2013). We aggregate the score of each class (i.e. sum of h + and h -regions) and each scale in a vector. Contrary to the original OB, we do not use SPM.

Our final representation is thus compact: S × K where S is the number of scales, and K is the number of classes. Ultimately, we use a linear SVM classifier for classification, because it enables to automatically learned the importance of each scale, and the correlations between the classes. Results for our multi-scale method are shown in Table 4.3. We first notice that performances improve compared to the best mono-scale results (Figure 4.2: 4 pt for MIT67, 7 pt for PPMI), validating the fact that taking into account different scales enable catching complementary and discriminative localized information. Then, we compare MANTRA to state-of-the-art works. We note that the improvement over part-based models, which use weaker features and essentially based on LSSVM (C.-N. [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 (B. [START_REF] Zhou | Learning Deep Features for Scene Recognition using Places Database[END_REF]). As we can verify, Places is better-suited for scene recognition (performance boost in 15-Scene and MIT67), whereas ImageNet has an edge over Places for object classification (PPMI). For UIUC, both models present similar performances. In Table 4.3, 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 mentioned earlier, internal representations learned by ConvNets present limited invariance power: learning strong invariance is therefore challenging (N. [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].

Ranking

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

Action Classification

We use standard (∼2400-dim) poselets as region features [START_REF] Behl | Optimizing Average Precision Using Weakly Supervised Data[END_REF], and there are about 20 regions per image. 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 annotations, we also evaluate detection performances to analyze the selected regions. We do not use the standard detection metric used in PASCAL VOC challenges, because it requires a good prediction of the object extend, which is not always possible with the poselets features of [START_REF] Behl | Optimizing Average Precision Using Weakly Supervised Data[END_REF]. We evaluate detection performances by measuring the averaged overlap between predicted and ground truth bounding box, which gives a coarse evaluation of the localization 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). 4.4, MANTRA-Acc outperforms LSSVM-Acc by ∼ 6 pt, again validating the relevance of the new model introduced in this chapter. MANTRA-Acc also performs similarly to LAPSVM, 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. We can also see that detection results are strongly correlated to ranking performances: MANTRA-AP also outperforms LAPSVM in terms of detection metric. 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 + .

Results

As shown in Table

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 hyper-parameter C We show in Figure 4.7 performance variations vs the regularization parameter C. We 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 note a large drop of performances when C is small. We also note that model optimizing AP during training are more robust to C parameter.

Object Recognition

Finally, we perform experiments on the PASCAL VOC 2007. We extract deep features pretrained 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 vgg-m-2048, after the ReLU. As done for the multi-class classification (Subsection 4.4.1.2), we extract deep features at different scales, and combine them with OB (L.-J. [START_REF] Li | Object Bank: An Object-Level Image Representation for High-Level Visual Recognition[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-of-the-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.5, 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. In [START_REF] Chatfield | Return of the Devil in the Details: Delving Deep into Convolutional Nets[END_REF], a 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.

Method

Conclusion

This chapter introduced a new latent structured output model, named MANTRA, dedicated to WSL of discriminative regions from images annotated with global labels. The MANTRA 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. We proposed an efficient cutting plane algorithm to train the model. We instantiated MANTRA for two different visual recognition tasks: multi-class classification and AP ranking. Another important contribution is the MANTRA AP ranking instantiation, for which efficient solutions are introduced to solve the challenging (loss-augmented) inference problem.

We evaluated MANTRA on the image classification task, where each region is represented by a deep feature. The experiments, carried out on six different datasets, validated the relevance of the proposed approach: MANTRA has good performances and training is fast. We showed that MANTRA outperforms deep features extracted on whole images, and WSL models using the maximum regions. In particular, on datasets evaluated with AP, we note a large performance improvement when the AP loss is optimized during training.

Unfortunately, extracting deep features for each region of an image is time consuming and inefficient. To address this problem, we propose in the next chapter to include MANTRA model in a deep ConvNet architecture.

Introduction

T o address the limited spatial invariance of ConvNets, we proposed in Chapter 4 a new WSL model (MANTRA) to learn discriminative regions from images annotated with global labels, where each region is represented by a deep feature extracted with a pre-trained model. Unfortunately, this strategy is highly inefficient since feature computations in (close) neighbor regions are not shared. To overcome this problem, we propose WEakly supervised Learning of Deep cOnvolutional neural Network (WELDON).

We design a fully convolutional network architecture which enables fast region feature computation by convolutional sharing (Section 5.3). As explained in Section 2.3, the key issue to WSL of deep ConvNets is to find how to pool the regions to get one score per map. The output of the ConvNet is a detection map for each category, so to train it with standard classification loss -since only image-level labels are available -, it is necessary to aggregate the maps into a global prediction for each class. The most popular approach is the max pooling, which selects the best region to perform prediction. Similarly to MANTRA, we propose in Subsection 5.3.2 a new pooling strategy based on negative evidence to automatically learn localized features. This pooling function generalizes MANTRA pooling function by selecting several maximum and minimum regions to be more robust. Contrary to the MANTRA model, the WELDON model can be trained end-to-end, which enables to fine-tune the whole network on the target dataset. Finally, we evaluate our model on six challenging datasets (Section 5.5), and analyze the impact of each improvement.

Generalized Negative Evidence Model

We introduce a new prediction function, which generalizes the MANTRA prediction function (Equation 4.3). We define a scoring function F w : X × Y × H → R, with depends on the input data x ∈ X , the output y ∈ Y, the latent variable h ∈ H and some parameters w ∈ R d . Our goal is to learn a prediction function f w , parametrized by w, so predicted output ŷ depends on F w (x, y, h).

As mentioned earlier, the main intuition of our negative evidence 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 ) corresponding to the maximum (resp. minimum) scoring latent value, for input x i and output y:

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

s w (x i , y) = F w (x i , y, h + i,y ) + F w (x i , y, h - i,y ) (5.2)
Finally, our prediction is:

ŷ = f w (x i ) = arg max y∈Y s w (x i , y) (5.3)
This maximization in Equation 5.3 is known as the inference problem. Regarding the soring function in Equation 5.2, we are here considering deep ConvNets models for f w . This generalizes the MANTRA model introduced in Chapter 4, using a log-linear scoring function: f w (x, y, h) = w, Ψ(x, y, h) where Ψ(x, y, h) is a joint feature map that describes the relation between input x, output y, and latent variable h.

WELDON Network Architecture

Based on the model presented in previous section, we propose WELDON, a new weakly supervised learning dedicated to learn localized visual features by using only image-level labels during training. The proposed network architecture is decomposed into two subnetworks: a deep feature extraction network based on VGG16 and a prediction network, as illustrated in Figure 5.1. The feature extraction net purpose is to extract a fixed-size deep descriptor for each region in the image, while the prediction network outputs a structured output.

Notation We note F l w (x, y, h) the output of the layer l at the location h of the feature map (or category) y for the input image x. w are the parameters of the ConvNet.

Feature Extraction Network

The feature extraction network is dedicated to computing a fixed-size representation for any region of the input image. When using ConvNets 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 ConvNet architectures trained on large scale databases such as ImageNet (e.g. 224 × 224). This is the approach followed in R-CNN (R. [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF], or in MANTRA (Chapter 4). This is, however, highly inefficient since feature computation in (close) neighbor regions is not shared. Recent improvements in SPPnet [START_REF] He | Spatial Pyramid Pooling in Deep Convolutional Networks for Visual Recognition[END_REF] or fast R-CNN (Ross Girshick 2015) process images of any size by using only convolutional/pooling layers of ConvNets trained on ImageNet, subsequently applying max pooling to map each region into a fixed-size vector. [START_REF] Long | Fully Convolutional Networks for Semantic Segmentation[END_REF] introduces the FCN.

The last fully connected layers of standard networks (AlexNet [START_REF] Krizhevsky | ImageNet Classification with Deep Convolutional Neural Networks[END_REF]), VGG16 [START_REF] Simonyan | Very Deep Convolutional Networks for Large-Scale Image Recognition[END_REF]) do not allow to have feature map with spatial resolution. The fully connected layers of these nets have fixed dimensions and throw away spatial coordinates. However, fully connected layers can also be viewed as convolutions with kernels that cover their entire input regions. Doing so casts these nets into fully convolutional networks that take input of any size and make spatial output maps. Convolutionalize fully connected layer allows to transfer fc6 representations, which are more discriminative features than conv5 representations. It also enables a faster computation, because the intermediate features over overlapping image regions are shared.

Our feature extraction network is based on VGG16 [START_REF] Simonyan | Very Deep Convolutional Networks for Large-Scale Image Recognition[END_REF]. The standard input image spatial size is 224 × 224, and with this input, the output spatial size of the feature map after conv5 is 7 × 7. We transform the fc6 as a convolution layer of 4096 filters 512 × 7 × 7 (called conv6). For an input image size 224 × 224, the feature map size after conv6 is 4096 × 1 × 1. For a larger input image h × w , the the feature map size after conv6 is 4096 × h × w, where h = h 32 -6 and w = w 32 -6. We show in Figure 5.1, the feature maps for an arbitrary input image size, and in dot line, we show the feature maps for the standard image size 224 × 224. In the proposed architecture, input images at a given scale are rescaled to a constant size I × I, 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 5.1). Input images are processed with the fully convolutional/pooling layers of ConvNets trained on ImageNet, leading to conv6 outputs of different sizes.

Prediction Network Design

We now present how to select the relevant regions to predict the global image label.

Transfer layer

The first layer of the prediction network is a transfer layer. Its goal is to transfer weights of the feature extraction network from large scale datasets to new target datasets. It transforms the output of the feature extraction network F f e into a feature map F t of size h × w × C, where C is the number of categories (see Figure 5.1). This layer is convolutional layer, composed of C filters, each of size 1 × 1 × 4096. Due to the kernel size of the convolution, this layer preserves the spatial resolution of the feature maps. The output of this layer can be seen as localization heatmaps. In Figure 5.1, we show the predicted regions for category car.

Weakly Supervised Prediction layer

The second layer is a spatial pooling layer s, which aggregates the score maps into classification scores: for each output y ∈ {1, . . . , C}, the score over the h × w regions are aggregated into a single scalar value. We note F t w (x i , y, h) is the score of region h from image x i for category y, and H = {1, . . . , r i } the region index set, and r i is the number of regions for image x i after the transfer layer. The output s of the prediction layer is a vector 1 × 1 × C. As mentioned earlier, the standard approach for WSL inherited from MIL is to select the max scoring region. The output score is the score of the region with the maximum score. In Subsection 4.2.1, we improve max pooling by incorporating negative evidence, and we show that negative evidence is important to have accurate predictions. We propose here to improve this strategy by using multiple regions.

WELDON Pooling

Based on recent MIL insights on learning with top instances (Subsection 2.2.1.2), we propose to extend MANTRA pooling by using multiple regions instead of single region. Using multiple regions allows to detect several objects or to identify the extent of an object. At the same time, (Bolei Zhou, Khosla, et al. 2016) proposes the Global Average Pooling (GAP) to identify all discriminative regions of an object. But, GAP pools over all regions, even non-relevant regions, while WELDON pools over a subset of selected regions. Formally, let h z ∈ {0, 1} be the binary variable denoting the selection of the z th region from layer F t . We propose the scoring function s top , which selects the k + highest scoring regions as follows:

s top w,k + (F t (x i , y)) = 1 k + r i ∑ z=1 h + z F t w (x i , y, z) (5.4)
where

h + = arg max h∈{0,1} r i r i ∑ z=1 h z F t w (x i , y, z) s.t. r i ∑ z=1 h z = k +
where F t w (x i , y) is the feature map for class y, and F t w (x i , y, z) is the value of the z th region score of feature map F t w (x i , y). Beyond the relaxation of the Negative Instances in Negative Bags (NINB) assumption, which is sometimes inappropriate (see Subsection 2.2.1.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.

To incorporate negative evidence in our prediction function, we propose the scoring function s low , which selects the k -lowest scoring regions as follows:

s low w,k -(F t (x i , y)) = 1 k - r i ∑ z=1 h - z F t w (x i , y, z) (5.5)
where

h -= arg min h∈{0,1} r i r i ∑ z=1 h z F t w (x i , y, z) s.t. r i ∑ z=1 h z = k -
The final prediction simply consists in summing s top and s low :

s w (x i , y) = s top w,k + (F t (x i , y)) + s low w,k -(F t (x i , y)) (5.6)
This prediction function is equivalent to MANTRA prediction function (Equation 4.3)

whenever k + = k -= 1.

Learning & Instantiations

As shown in Figure 5.1, the WELDON model outputs s ∈ 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 section, we consider three different structured prediction tasks, and their associated loss functions during training.

Classification

Multi-class classification In this simple case, C is the number of classes and the output space is Y = {1, . . . , C}. We use the usual softmax activation function on top of the spatial aggregation s. The probability of class y for image x is: P(y|x) = exp(s w (x, y))/ ∑ y ∈Y exp(s w (x, y )) 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(y|x) = (1 + exp(-s w (x, y))) -1 , with its associated log loss.

Ranking: Average Precision

We also tackle the problem of optimizing ranking metrics, and especially Average Precision (AP). We use similar notations that in Subsection 4.3.2. The goal is to predict a ranking matrix y. For the ranking model, we assume that k + = k -= k. We define the scoring ranking function for category c as follow

s c w (x, y) = s top w,k (x, y, c) + s low w,k (x, y, c) (5.7) s top w,k (x, y, c) = max h ∑ p∈P ∑ n∈N y pn r p ∑ z=1 h pn z F t w (x p , c, z) - r n ∑ z =1 h np z F t w (x n , c, z ) (5.8) s low w,k (x, y, c) = min h ∑ p∈P ∑ n∈N y pn r p ∑ z=1 h pn z F t w (x p , c, z) - r n ∑ z =1 h np z F t w (x n , c, z ) (5.9)
where P (resp. N ) is the set of positive (resp. negative) examples, r p is the number of regions for image p, h pn (resp. h np ) is a vector, which represents the selected region for image p (resp. n) when we consider the couple of images (p, n), and

h = {(h pn , h np ) ∈ {0, 1} r p × {0, 1} r n , r p ∑ z=1 h pn z = k, r n ∑ z=1 h np z = k, (p, n) ∈ P × N } (5.10)
During training, we aim at minimizing the following loss: ∆ AP (y , y) = 1 -AP(y , y), where y is the ground-truth ranking. Since AP is non-smooth, we use the following surrogate (upper-bound) loss:

L w (x, y ) = max y∈Y [∆ AP (y , y) + s c w (x, y)] -s c w (x, y ) (5.11)
The maximization is generally called Loss-Augmented Inference (LAI). Exhaustive maximization is intractable due to the huge size of the structured output space. The problem is even exacerbated in the WSL setting, see [START_REF] Behl | Optimizing Average Precision Using Weakly Supervised Data[END_REF]. We exhibit here the following result for WELDON:

Proposition 5.1. For each training example, let us denote s(i) = s top w,k (F t w (x i , c)) + s low w,k (F t w (x i , c)) in Equation 5.6. Inference and LAI for the WELDON ranking model can be exactly solved by sorting examples in descending order of score s(i).

Proof. We will show that the inference is equivalent to a supervised inference, where each image x i is represented by s top w,k (F t w (x i , c)) + s low w,k (F t w (x i , c)). We first show that it is possible to decouple the optimization over the ranking matrix y and the predicted regions h:

s w (x, y) = s top w,k (x, y, c) + s low w,k (x, y, c) (5.12) = max h ∑ p∈P ∑ n∈N y pn r p ∑ z=1 h pn z F t w (x p , c, z) - r n ∑ z =1 h np z F t w (x n , c, z ) + min h ∑ p∈P ∑ n∈N y pn r p ∑ z=1 hpn z F t w (x p , c, z) - r n ∑ z =1 hnp z F t w (x n , c, z ) (5.13) = ∑ p∈P ∑ n∈N max (h pn ,h np ) y pn r p ∑ z=1 h pn z F t w (x p , c, z) - r n ∑ z =1 h np z F t w (x n , c, z ) + min ( hpn , hnp ) y pn r p ∑ z=1 hpn z F t w (x p , c, z) - r n ∑ z =1 hnp z F t w (x n , c, z ) (5.14)
The maximization (resp. minimization) can be decomposed for each term of the sum, so maximizing (resp. minimizing) the sum is equivalent to maximize (resp. minimize) each term of the sum. Now, we analyze the predicted regions with respect to y pn value. We notice that the predicted regions are the same in the two cases: the predicted regions can be fixed independently to the value of y pn . The inference can be written as a supervised inference, where the region are fixed independently to the ranking matrix y, and each image x i is represented by

s top w,k (F t w (x i , c)) + s low w,k (F t w (x i , c)).
Proposition 5.1 shows that the optimization over regions, i.e. score s(i), decouples from the maximization over output variables y. This reduces inference and LAI optimization to fully supervised problems. Inference solution directly corresponds to s(i) sorting. It also allows to use our model 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.

Optimization

Our model is based on a deep architecture. We initialize it from a model pre-trained on ImageNet [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF] and train it with Stochastic Gradient Descent (SGD) with momentum (Subsection 2.1.2.2) with image-level labels only. All the layers of the network are fine tuned. For multi-class and multi-label predictions, error gradients are well-known. For the ranking instantiation, given a class c, we detail the gradient:

∂L ∂w = ∂s c w (x, ỹ) ∂w - ∂s c w (x, y ) ∂w (5.20)
where ỹ is the LAI solution. The gradient of s c w (x, y) with respect to w is:

∂s c w (x, y) ∂w = ∑ p∈P ∑ n∈N y pn r p ∑ z=1 (h p+ z + h p- z ) ∂F t w (x p , c, z) ∂w + r n ∑ z =1 (h n+ z + h n- z ) ∂F t w (x n , c, z ) ∂w (5.21)
where the latent variables for example i are:

h i+ = max h r i ∑ z=1 h z F t w (x i , c, z), s.t. r i ∑ z=1 h z = k ∀z ∈ {1, . . . , r i } h z ∈ {0, 1} (5.22)
h i-= min h r i ∑ z=1 h z F t w (x i , c, z), s.t. r i ∑ z=1 h z = k ∀z ∈ {1, . . . , r i } h z ∈ {0, 1} (5.23)
When learning WELDON, the gradients are back-propagated through the spatial pooling layer only within the selected regions, all other gradients being discarded. The selection of relevant regions for back-propagation is a key to learn precisely localized features without any spatial supervision (C. Sun et al. 2016).

Experiments

In this section, we first analyze our model (Subsection 5.5.1), and then compare it to stateof-the-art methods (Subsection 5.5.2). We now briefly present some experimental details.

Our deep ConvNet 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 . These datasets are presented in Section 2.4. We first provide an analysis of our method on four datasets, and then, we compare it with state-of-the-art methods.

WELDON Analysis

In this section, we analyze the impact on prediction performances of the different contributions of WELDON given in Section 5.3 and Section 5.4. Our baseline model a) is the WSL ConvNet model using an aggregation function s=max at the pooling stage, 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 WELDON and a), we perform a systematic evaluation on the performance when the following variations are incorporated: e) Fine-tuning (FT) of the network on the target dataset.

The results are reported in Table 5.2 for object and context datasets with AP evaluation (VOC 2007 and VOC 2012 action), and in Table 5.3 for scene datasets. From this systematic evaluation, we can draw the following conclusions:

• Both b) and c) improvements result in a very large performance gain on all datasets, with a comparable impact on performances: about +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. Note that this model is equivalent to MANTRA with VGG16 deep features.

• 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 negative evidence and top instances. We perform an additional experiment for comparing b)+c) and c), by setting the same number of regions (e.g. 6max and 3-max+3-min). It turns out that k + -max+k --min is the best method for various k + /k -values, showing that negative evidence contains significant information for visual prediction.

• Similarly to MANTRA experiments (Subsection 4.4.2), we note that 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. Finally, we show in Figure 5.2 the performance in different configurations, corresponding to sequentially adding the previous improvements in the following order: a), a)+b), a)+b)+c), and a)+b)+c)+d) for VOC 2007 / VOC 2012 / VOC 2012 Action and a)+b)+c)+e) for MIT67 and 15 Scene. On all dataset, we can see the very large improvement from configuration a) to configuration a)+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. Note that the analysis of the number of selected regions is done in the next chapter (Subsection 6.5.2).

Qualitative analysis of region selection

To illustrate the region selection policy performed by WELDON, we show in Figure 5.3 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 evidences for the class, e.g. parts of coach strongly penalize the prediction of the class horse, or seat or handlebar negatively supports the prediction of the sofa category.

Comparison with State-of-the-Art Methods

We now compare the WELDON model to state-of-the-art methods. We use the multi-scale WSL model described in Subsection 5.3.1, and we use the same scale combination that in Section 4.4. For the selection of top/low instances, we use here the default setting of k + = k -= 3, for scale α ≤ 70% (Table 5.1). Results for object (resp. scene and context) datasets are gathered in Table 5.4 (resp. For object datasets, we can show in Table 5.4 that WELDON 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. 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 about 8 pt on VOC 2007 highlights the superiority of region selection based on supervised information, rather than using handcrafted aggregation with SPM strategy. Then, we compare WELDON to recent WSL methods based on deep features: Deep MIL [START_REF] Oquab | Is object localization for free? -Weakly-supervised learning with convolutional neural networks[END_REF] The results shown in Table 5.5 for scene recognition also illustrate the significant 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] 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 ConvNet training with WELDON. Note that WELDON outperforms MANTRA, which used deep features trained on Places.

In Table 5.6, we show the results in datasets where contextual information is important for performing prediction. On VOC 2012 action and MS 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 MS 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 prediction 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 MS COCO also illustrate the efficiency of the proposed WSL training of deep ConvNet with WELDON, which is able to deal with this large dataset (80 classes and ∼ 80, 000 training examples).

Conclusion

In We showed the excellent performances of our model on very different visual recognition tasks: object class recognition, scene classification, including images with a cluttered context, outperforming state-of-the-art results on six challenging datasets. The analysis of our model on four datasets showed that both negative evidence and top instance are relevant and complementary.

We showed that using several regions is important to have robust predictions. In our experiments, we gave the same importance of the positive and negative evidence terms, i.e. k + = k -. Maximum and minimum scoring regions are complementary, but there is no obvious reason that they should have the same importance. In the next chapter, we introduce a more general aggregation strategy, that controls the relative importance of the positive and negative evidence terms.

Chapter abstract

This chapter introduces WILDCAT, a method to learn localized visual features related to class modalities. WILDCAT extends WELDON (Chapter 5) at three major levels: the use of Fully Convolutional Network (FCN) for maintaining spatial resolution, the explicit design in the network of local features related to different class modalities, and a new way to pool these features to provide a global image prediction required for Weakly Supervised Learning (WSL). The proposed model is used to perform image classification as well as weakly supervised pointwise object localization and segmentation.

The work in this chapter has led to the publication of a conference paper:

• Thibaut [START_REF] Durand | WILD-CAT: Weakly Supervised Learning of Deep ConvNets for Image Classification, Pointwise Localization and Segmentation[END_REF]. "WILDCAT: Weakly Supervised Learning of Deep ConvNets for Image Classification, Pointwise Localization and Segmentation". In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR)

Introduction

G lobal spatial pooling is a crucial step for WSL of deep ConvNets with image-level labels. In the Chapter 5, we introduced WELDON pooling, which explicitly encodes negative evidence and top instance strategy. In this chapter, we propose a new pooling function, which generalizes WELDON pooling by introducing a relative weight between max and min regions. In Section 6.5, we also propose a unified framework for pooling, which generalizes standard WSL pooling functions as special cases, including our model. This analysis of pooling functions is supplemented by a detailed experimental comparison on six datasets.

WILDCAT Model

The overall WILDCAT architecture (Figure 6.2) is based on a FCN which is suitable for spatial predictions [START_REF] Long | Fully Convolutional Networks for Semantic Segmentation[END_REF], a multi-map WSL transfer layer encoding modalities associated with classes, and a global pooling for WSL that learns accurate localization. We now delve into each of the three parts of the model.

Fully Convolutional Architecture

The selection of relevant information within feature maps is a major issue in WSL. It impacts the localization of the learned representation and the precision of the results (e.g. semantic segmentation or object detection). We thus expect the resolution of the feature maps to be a key component for WILDCAT: finer maps keep more spatial resolution and lead to more specific regions (e.g. objects, parts).

To this end we exploit the recently introduced FCN ResNet-101 [START_REF] He | Deep Residual Learning for Image Recognition[END_REF]) (left of Figure 6.2) that naturally preserves spatial information throughout the network. It also computes local features from all the regions in a single forward pass, without resizing them. Besides, ResNet architectures are effective at image classification while being parameter-and time-efficient [START_REF] He | Deep Residual Learning for Image Recognition[END_REF]. This kind of architecture has been exploited to speed up computation and to produce accurate spatial predictions in fully supervised setups, e.g. in object detection (Dai, Y. Li, et al. 2016) and semantic segmentation (Dai, He, et al. 2016).

We use the publicly released model pre-trained on ImageNet dataset [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF] and remove the last layers (global average pooling and fully connected) to replace them with WSL transfer and wildcat pooling layers (Figure 6.3) described in the following. Local features are then aggregated with a global spatial pooling to yield a single score per class.

Multi-map Transfer Layer

We introduce a multi-map WSL transfer layer that learns multiple class-related modalities, encoded into M feature maps per class through 1 × 1 convolutions (middle of Figure 6.2).

The modalities are learned in a WSL fashion with only the image-level labels and the transfer layer keeps spatial resolution, key in WSL. We note w × h × d the size of conv5 maps of ResNet-101, which is W 32 × H 32 × 2048 for an original image of size W × H × 3. The transfer output is then of size w × h × MC (Figure 6.3). Given an example x, we note F multi w (x, (y, m), h) the output of the m-th map of class y at location h. The M modalities aim at specializing to different class-specific features, e.g. parts (Dai, He, et al. 2016;Dai, Y. Li, et al. 2016) (head and legs of dog in Figure 6.1) or views [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF]Ross Girshick et al. 2015). We highlight differences with some specific encoding approaches: position-sensitive Region-of-Interest (RoI) pooling in Region-based Fully Convolutional Network (R-FCN) (Dai, Y. Li, et al. 2016) forces position-based specialization (relative to the object) while our method can also learn other kind of features, e.g. semantic parts (Figure 6.1). In the same way DPM [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF]) learns only discriminating parts where our multi-map transfer model can find more general features, e.g. context. Furthermore, contrarily to the DPM where a different model is learned for each view, we share most of the computation within the FCN, which is more efficient.

Learning multiple modalities allows to fully exploit available spatial resolution by making a better use of all the information contained at each location. We note that when M = 1 this reduces to a standard classification layer, i.e. into C classes. We empirically show that M > 1 yields better results than regular M = 1.

Wildcat Pooling

WILDCAT learns from image-level labels so we need a way to summarize all information contained in the feature maps for each class (right of Figure 6.2). We note that there are no more learned parameters in this pooling layers, which means we can directly interpret and visualize feature maps at this level (Bolei Zhou, Khosla, et al. 2016;Dai, Y. Li, et al. 2016).

We perform this in two steps (Figure 6.3): a class-wise pooling (Equation 6.2) that combines the M maps from the multi-map transfer layer, then a spatial pooling module (Equation 6.1) that selects relevant regions within the maps to support predictions. This leads to wildcat pooling, a two-stage pooling operation to compute the score s w (x, y) of class y given an input x: Class-wise pooling The first step consists in combining the M maps for all classes independently, and is described in Equation 6.2 with a generic pooling function Cl. Pool. We use average pooling in the following. The maps are transformed from w × h × MC to w × h × C (Figure 6.3). When M = 1 this operation is not needed as each class is already represented by a single map.

s w (x, y) = Sp. Pool h∈H F t w (x, y, h) (6
We note that even if a multi-map followed by an average pooling is functionally equivalent to a single convolution (i.e. M = 1), the explicit structure it brings with M modalities has important practical advantages making training easier. We empirically show that M > 1 yields better results than regular M = 1.

Spatial pooling

We now introduce our new spatial aggregation method implementing the second, spatial pooling step (Equation 6.1) for each map y:

s w (x, y) = s top w,k + (F t w (x, y)) + α • s low w,k -(F t w (x, y)) (6.3)
where F t w (x, y) is the score map for category y and s top w,k + (resp. s low w,k -) are defined in Equation 5.4 (resp. Equation 5.5), and α ∈ [0, 1] is a trade off parameter. It consists in selecting for each class y the k + (resp. k -) regions with the highest (resp. lowest) activations from input zc . The output s w (x, y) for class y of this layer is the weighted average of scores of all the selected regions. We only consider regions defined by single neurons in the convolutional feature maps.

Maximum and minimum scoring regions both are important for good results, but do not bring the same kind of information. We explore relative weighting of both types of regions by introducing a factor α which trades off relative importance between both terms. We hypothesize that maximum scoring regions are more useful for classification as they directly support the decision, while minimum scoring regions essentially act as regularization. With α < 1 WILDCAT should focus more on discriminating regions and then better localize features than with α = 1. (Bolei Zhou, Khosla, et al. 2016) can be obtained with more. Drawing from negative evidence [START_REF] Parizi | Automatic discovery and optimization of parts for image classification[END_REF], we can incorporate minimum scoring regions to support classification and our spatial pooling function can reduce to the WELDON pooling (Chapter 5).

Architecture Discussion

WILDCAT architecture is composed of a transfer layer followed by pooling. Since there are no parameters to learn in the pooling module, the transfer layer performs classification and it is easy to visualize heatmaps with direct localization of discriminating regions (Figure 6.4 second row). We note that this kind of architecture is reversed in (Bolei [START_REF] Zhou | Learning Deep Features for Discriminative Localization[END_REF] where pooling is performed before the last fully connected layer (Figure 6 It is shown in (Bolei Zhou, Khosla, et al. 2016) that if the spatial aggregation method is linear, e.g. Global Average Pooling (GAP), then the order of both layers is not important, but the two configurations can behave differently with a non linear pooling function such as wildcat spatial pooling. The difference is more significant when k + + k -is low, i.e. when wildcat spatial pooling really differs from global average pooling. We evaluate the impact of this design choice and of the chosen pooling function in the experiments and show that our architecture yields better results.

WILDCAT Applications

Training phase Our WILDCAT model is based on the backbone architecture ResNet-101 [START_REF] He | Deep Residual Learning for Image Recognition[END_REF]). We initialize it from a model pre-trained on ImageNet [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF] and train it with Stochastic Gradient Descent (SGD) with momentum with image-level labels only. All the layers of the network are fine-tuned. The input images are warped to a square size at a given scale. We use a multi-scale setup where a different model is learned for each scale and they are combined with Object Bank (OB) (L.-J. [START_REF] Li | Object Bank: An Object-Level Image Representation for High-Level Visual Recognition[END_REF] strategy.

WILDCAT is designed to learn from image-level supervision only: the same training procedure is used for image classification, weakly supervised object detection and weakly supervised semantic segmentation. When learning WILDCAT, the gradients are backpropagated through the wildcat layer only within the k + + k -selected regions, all other gradients being discarded. The selection of right regions for back-propagation is key to learn precisely localized features without any spatial supervision (C. Sun et al. 2016).

Inference phase Predictions differ according to the task at hand. For image classification, prediction simply takes the single-value output of the network (like in training). Object detection and semantic segmentation require spatial predictions so we extract the classspecific maps before spatial pooling to keep spatial resolution. They are at resolution 1 32 with respect to the input image for ResNet-101 architecture [START_REF] He | Deep Residual Learning for Image Recognition[END_REF]. For weakly supervised object detection, we extract the region (i.e. neuron in the feature map) with maximum score for each class and use it for point-wise localization, as it is done in [START_REF] Oquab | Is object localization for free? -Weakly-supervised learning with convolutional neural networks[END_REF][START_REF] Bency | Weakly Supervised Localization using Deep Feature Maps[END_REF]. For weakly supervised semantic segmentation we compute the final segmentation mask either by taking the class with maximum score at each spatial position independently or by applying a CRF for spatial prediction as is common practice (L. [START_REF] Chen | Semantic Image Segmentation with Deep Convolutional Nets and Fully Connected CRFs[END_REF][START_REF] Pathak | Constrained Convolutional Neural Networks for Weakly Supervised Segmentation[END_REF].

Classification Experiments

In order to get results in very different recognition contexts, several datasets are used: object recognition (Pascal VOC 2007, Pascal VOC 2012, MS COCO), scene categorization (MIT67), action recognition (Pascal VOC 2012 Action) and fine-grained recognition (CUB-200). These datasets are presented in Section 2.4. We first analyze the hyper-parameters of our model on three datasets (Subsection 6.3.1), and then, we compare it to state-of-the-art methods on six datasets (Subsection 6.3.2).

WILDCAT Analysis

In this section, we analyze the impact of our contributions on three datasets: VOC 2007, VOC 2012 Action and MIT67. We study our network architecture, the impact of the weighting hyper-parameter α and the number of modalities M per class. We present results for an input image of size 448 × 448 and k + = k -= 1, but similar behaviors are observed for other scales and larger k + and k -. By default, our model parameters α and M are fixed to 1.

Deep Structure

Firstly, to validate the design choice of the proposed WILDCAT architecture, we evaluate two different configurations presented in Subsection 6.2.5:

(a) conv5 + conv + pooling (our architecture);

(b) conv5 + pooling + conv (architecture proposed in (Bolei [START_REF] Zhou | Learning Deep Features for Discriminative Localization[END_REF]).

These two configurations are different for the non-linear WILDCAT pooling scheme described in Subsection 6.2.3, and their comparison is reported in Table 6.2. We can see that our architecture (a) leads to a consistent improvement over architecture (b) used in GAP (Bolei Zhou, Khosla, et al. 2016) Table 6.2.: Classification performances for architectures (a) and (b).

Impact of Parameter α

We investigate the effect of the weighting hyper-parameter α on classification performances. From the results in Figure 6.5, it is clear that incorporating negative evidence, i.e.

α > 0, is beneficial for classification, compared to standard max pooling, i.e. α = 0. We further note that using different weights for maximum and minimum scores, i.e. α = 1, yields better results than with α = 1 (i.e. WELDON), with best improvement of 1.6 pt (resp. 2 and 1.8) with α = 0.6 (resp. 0.7 and 0.8) on VOC 2007 (resp. VOC 2012 Action and MIT67). This confirms the relevance of using a relative weighting for negative evidence. Moreover our model is robust with respect to the value of α. Table 6.3.: Analysis of multi-map transfer layer.

Ablation Study

We perform an ablation study to illustrate the effect of each contribution. Our baseline is a WSL transfer with M = 1 and the spatial pooling with α = 1. The results are reported in Table 6.4. From this ablation study, we can draw the following conclusions:

• Both α = 0.7 and M = 4 improvements result in large performance gains on all datasets; [START_REF] Parizi | Automatic discovery and optimization of parts for image classification[END_REF], MANTRA, WELDON. This shows the improvement brought out by the WILDCAT network architecture. This validates that our region selection approach is better than using all regions. WILDCAT also significantly outperforms, on CUB-200 and MIT67, the recent GoogLeNet-GAP (Bolei [START_REF] Zhou | Learning Deep Features for Discriminative Localization[END_REF], which used a global average pooling. On CUB-200, we can also

We also reported results for different ResNets. The ResNet-101 is directly comparable to our model, because it corresponds to our initial model. It is important to note that with the same number of parameters and a very similar architecture, our model have a significant performance gain with respect to ResNet-101 (1 crop): +3.2 pt (resp. +2.0) on top-1 (resp. top-5) error. We also report the results with multi-crops post-processing, which a widely used post-processing to boost performances. Compared to our approach, multi-crops strategy extracts regions with a fixed grid, whereas our model automatically selects relevant regions. The important gain validates the relevance of our region selection approach. We also compare our model to deeper ResNet models: WILDCAT is +0.9 pt (resp. +0.7) better than the deeper model ResNet-200, which have about the double of parameters. We can also note that WILDCAT prediction is simple because it needs only 1 forward on the image to predict image label, whereas the multi-crops prediction needs several forwards on different image regions.

Weakly Supervised Experiments

In this section, we show that our model can be applied to various tasks, while being trained from global image labels only. We evaluate WILDCAT for two challenging weakly supervised applications: localization and segmentation. In this section, we use a mono-scale setup, with an input image size 448 × 448.

Weakly Supervised Localization

We evaluate the localization performances of our model on PASCAL VOC 2012 validation set [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2012[END_REF]) and MS COCO validation set (T.-Y. [START_REF] Lin | Microsoft COCO: Common Objects in Context[END_REF]. The performances are evaluated with the point-based object localization metric introduced by [START_REF] Oquab | Is object localization for free? -Weakly-supervised learning with convolutional neural networks[END_REF]. This metric measures the quality of the detection, while being less sensitive to misalignments compared to other metrics such as Intersection-over-Union (IoU) [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2012[END_REF], which requires the use of additional steps (e.g. bounding box regression). WILDCAT localization performances are reported in Table 6.9. Our model significantly outperforms existing weakly supervised methods. We can notice an important improvement between WILDCAT and MIL-based architecture Deep MIL [START_REF] Oquab | Is object localization for free? -Weakly-supervised learning with convolutional neural networks[END_REF], which confirms the relevance of our spatial pooling function. In spite of its simple and multipurpose architecture, our model outperforms by a large margin the complex cascaded architecture of ProNet (C. Sun et al. 2016). It also outperforms the recent weakly supervised model [START_REF] Bency | Weakly Supervised Localization using Deep Feature Maps[END_REF] Note that since the localization prediction is based on classification scores, good classification performance is important for robust object localization. In Figure 6.6, we evaluate the classification and localization performances with respect to α on VOC 2012. Both classification and localization curves are very similar. The best localization performances are obtained for α ∈ [0.6, 0.7], and the improvement between α = 1 and α = 0.7 is 1.6 pt. We can note that the worst performance is obtained for α = 0, which confirms that the contextual information brought by the minimum is useful for both classification and localization.

Weakly Supervised Segmentation

We evaluate our model on the PASCAL VOC 2012 image segmentation dataset (Everingham, [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2012[END_REF], consisting of 20 foreground object classes and one background class. We train our model with the train set (1,464 images) and the extra annotations provided by [START_REF] Hariharan | Semantic contours from inverse detectors[END_REF]) (resulting in an augmented set of 10,582 images), and test it on the validation set (1,449 images). The performance is measured in terms of pixel Intersection-over-Union (IoU) averaged across the 21 categories. As in existing methods, we add a Fully Connected CRF (FC-CRF) [START_REF] Krähenb Ühl | Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials[END_REF] to post-process the final output labeling.

Segmentation results

The result of our method is presented in Table 6.10. We compare it to weakly supervised methods that use only image labels during training. We can see that WILDCAT without FC-CRF outperforms existing weakly supervised models by a large margin. We note a large gain with respect to MIL models based on (soft-)max pooling [START_REF] Pathak | Fully Convolutional Multi-Class Multiple Instance Learning[END_REF]Pedro O. Pinheiro and Collobert 2015), which validates the relevance of our pooling for segmentation. The improvement between WILDCAT with FC-CRF and the best model is 7.1 pt. This confirms the ability of our model to learn discriminative and accurately localized features. We can note that all the methods evaluated in Table 6.10 have comparable complexity.

Method

Mean IoU MIL-FCN [START_REF] Pathak | Fully Convolutional Multi-Class Multiple Instance Learning[END_REF] 24.9 MIL-Base+ILP+SP-sppxl (Pedro O. Pinheiro and Collobert 2015) 36.6 EM-Adapt + FC-CRF (Papandreou, L.-C. Chen, et al. 2015) 33.8 CCNN + FC-CRF [START_REF] Pathak | Constrained Convolutional Neural Networks for Weakly Supervised Segmentation[END_REF] 35 With a quite more complex strategy, the very recent paper [START_REF] Kolesnikov | Seed, Expand and Constrain: Three Principles for Weakly-Supervised Image Segmentation[END_REF]) presents impressive results (50.7 MIoU). The training scheme in [START_REF] Kolesnikov | Seed, Expand and Constrain: Three Principles for Weakly-Supervised Image Segmentation[END_REF] incorporates different terms, which are specifically tailored to segmentation: one enforces the segmentation mask to match low-level image boundaries, another one incorporates prior knowledge to support predicted classes to occupy a certain image proportion.

In contrast, WILDCAT uses a single model which is trained in the same manner for the three tasks, i.e. classification, localization and segmentation. Our model could certainly benefit a lot from the specific terms used in [START_REF] Kolesnikov | Seed, Expand and Constrain: Three Principles for Weakly-Supervised Image Segmentation[END_REF] to further improve performances for the segmentation task.

Qualitative Results

In Figure 6.7, we show predicted segmentation masks for four images. Compared to ground truth ((b) column), we can see that our predicted segmentation masks ((e) column) are always relevant, except for the last example where the rails and the train are glued together. The heatmaps from the same class (columns (c) and (d)) show different modalities learned by our model. When successful, they focus on different parts of the objects. For example, on the first row, the heatmap (c) focuses on the head of the bird whereas the heatmap (d) focuses on the legs and the tail.

Pooling Analysis

In this section, we analyze the spatial pooling. We first propose an unified pooling framework to compare standard WSL pooling functions. Then, this analysis is supplemented by a detailed experimental comparison on six datasets.

Generalized Pooling Model

To put into perspective connections between negative evidence and existing pooling strategy used in latent structured models, we introduce the following generalized scoring function, with "inverse temperature" β + h and β - h parameters smoothing between max, softmax and average:

s (α,β + h ,β - h ) w (x, y) = 1 2β + h log 1
|H| ∑ h∈H exp[β + h F w (x, y, h)] (6.4)

+ α 1 2β - h log 1 |H| ∑ h∈H exp[β - h F w (x, y, h)]
As shown in Table 6.11, this generalized scoring function (Equation 6.4) includes several existing models as special cases. First, we fix α = 1. When β + h = β - h → +∞, it maximizes over latent variables and is equivalent to LSSVM (C.-N. [START_REF] Yu | Learning Structural SVMs with Latent Variables[END_REF] or max pooling for deep ConvNets [START_REF] Oquab | Is object localization for free? -Weakly-supervised learning with convolutional neural networks[END_REF]. When β + h = β - h = 1, is is equivalent HCRF [START_REF] Quattoni | Recognizing indoor scenes[END_REF] or MSSVM [START_REF] Ping | Marginal Structured SVM with Hidden Variables[END_REF], which marginalize over latent variables. GAP (Bolei Zhou, Khosla, et al. 2016) (β + h = β - h → 0) also sum over latent variables, but unlike HCRF or MSSVM, all the latent variables have the same importance. The -framework [START_REF] Schwing | Efficient Structured Prediction with Latent Variables for General Graphical Models[END_REF]) / Log-Sum-Exp (LSE) pooling (Pedro O. Pinheiro and Collobert 2015;C. Sun et al. 2016) propose a trade-off between max and average. This pooling function is equivalent to the generalized pooling function when β + h = β - h ∈ [1, +∞). We can also see that pooling function as a soft pooling function of top instance model (W. [START_REF] Li | Multiple Instance Learning for Soft Bags via Top Instances[END_REF] and Learning with Label Proportion (LLP) (F. X. [START_REF] Yu | ∝SVM for Learning with Label Proportions[END_REF].

To incorporate negative evidence in the generalized pooling function, β - h must be negative. When β + h → +∞ and β - h → -∞, the generalized pooling function is equivalent The x-axis shows the proportion of selected regions and the y-axis the performance. We can see that MANTRA always outperforms the max pooling, which validates the relevance of negative evidence. We can also see that our spatial outperforms equally or better than GAP with only 20 % of regions.

robust than using only the best region. We also note that LSE pooling performances are closed to MANTRA pooling performances. MANTRA pooling, which used only 2 regions, is as efficient as the LSE pooling which used all regions. Except on MS COCO, we observe that the GAP is better than LSE which is better than max: using more regions increase the robustness. On MS COCO, we see that the region selection is important because a lot of objects have small sizes: the gain is +3 pt between WELDON with 20 % of regions and GAP.

Conclusion

In this chapter, we proposed WILDCAT, a new WSL model dedicated to learning discriminative localized visual features by using only image-level labels during training.

WILDCAT extends WELDON at three major levels: the use of FCN for maintaining spatial resolution, the explicit design in the network of local features related to different class modalities, and a new way to pool these features to provide a global image prediction required for weakly supervised training. We also introduced a unified framework for pooling, which generalizes standard WSL models as special cases, including our model. Extensive experiments showed the effectiveness of WILDCAT on image classification, for which we report outstanding performances on six challenging datasets. We also showed that our framework can be used to improve the performance of state-of-the-art deep models for large-scale image classification on ImageNet. We showed that our model can be efficiently applied to weakly supervised applications (pointwise localization and segmentation), while being trained from global image labels only. Finally, the spatial pooling analysis showed that the number of regions is crucial for good performances. We observed that for scene datasets we need a large number of regions whereas on datasets with small objects we need a small number of regions. Our experiments on ImageNet also showed that fine-tuning a pre-trained network with our WSL architecture leads to a significant performance gain. It would be instesting to learn our WSL network on large-scale datasets from scratch, e.g. on ImageNet or Places2. whole architecture is carefully designed for fast processing by sharing region feature computations and allows end-to-end training. In Chapter 6, we extended WELDON by introducing WILDCAT, a new architecture based on a new multi-map transfer layer, which automatically learns several class specific modalities. Unlike WELDON, this architecture is based on the Fully Convolutional Network (FCN) ResNet-101, which allows to learn feature maps with more accurate resolution than WELDON. We also showed that this architecture is multipurpose and can be efficiently used for image classification as well as weakly supervised pointwise object localization and segmentation.

Future Work

Pooling for WSL

The analysis of pooling functions shows that the number of maps per class and the number of selected regions are important hyper-parameters. We think that it would be interesting to learn these hyper-parameters.

In this manuscript, we showed that using several maps per class to learn multiple class-related modalities is an interesting approach. In our experiments, the number of maps is fixed for all the classes, but different classes have different complexities and therefore may not be well modeled by a fixed number of parts. Indeed, learning several modalities is useful for objects that can be represented as a collection of parts, e.g. a car has wheels, doors, windows, mirrors, license plates. On the contrary, using several modalities on objects without part (e.g. TV monitor) is not efficient, because there is only one modality. We think that learning a specific number of maps for each class is a promising research direction to improve classification performances. A method to achieve this is to use a 1 -normalized weighted average of the maps to keep only the relevant maps for each class [START_REF] Kulkarni | Learning the Structure of Deep Architectures Using L1 Regularization[END_REF].

Other important hyper-parameters are the numbers of selected regions k + & k -in the spatial pooling. Our experiments showed that the optimal number of regions depends on the task. For scene datasets we need a lot of regions because the context information is relevant. On the contrary for object datasets with complex scenes and small objects we need few regions to select relevant regions only. Another limitation is that the numbers of selected regions k + & k -are fixed for all classes. It would be more interesting to learn different numbers of regions per class, because some object classes are naturally bigger (e.g. aeroplane > person > bottle), and the context can be very important for some classes.

Deep learning for complex images

Spatial resolution of the detection maps Our models use the outputs of the last convolution layers as feature representations, but the spatial information in these layers is too coarse to allow precise localization. However, having feature maps with high spatial resolution is crucial to deal with complex images, because the objects can be at different locations and can be very small. For example on MS COCO, 41% of the objects are small, i.e. their areas are less than 0.4% of the whole image area. To deal with small objects, we need dense feature maps. A solution to generate both high-resolution and semantic feature maps is to combine predictions from different layers in a ConvNet, e.g. Hypercolumns [START_REF] Hariharan | Hypercolumns for Object Segmentation and Fine-grained Localization[END_REF], Inside-Outside Net [START_REF] Bell | Inside-Outside Net: Detecting Objects in Context with Skip Pooling and Recurrent Neural Networks[END_REF], Feature Pyramid Network (FPN) (T.-Y. [START_REF] Lin | Feature Pyramid Networks for Object Detection[END_REF]. Another strategy is to use dilated convolutions to reduce the number of spatial pooling layers in the network (L. [START_REF] Chen | Semantic Image Segmentation with Deep Convolutional Nets and Fully Connected CRFs[END_REF]. It would also be interesting to use multi-scale feature maps, to detect objects at different scales.

Applications to WSL tasks

We showed that our model can be successfully used for weakly supervised pointwise object localization. However, it cannot be directly applied to predict object bounding boxes, because the sizes of the regions are implicitly fixed by the network architecture. This architecture enables fast feature region computation, but does not allow to deal with arbitrary region sizes. To be effective on detection task, we need regions with different sizes and aspect ratios. A potential future direction would be to study how we can adapt popular detection models to our task. We also showed that our generic architecture has competitive results on weakly supervised semantic segmentation task. On the contrary, the state-of-the-art method uses a more complex strategy, specifically tailored to segmentation, e.g. a loss to constrain the segmentations to match with object boundaries. To improve the segmentation performances, our model could certainly benefit a lot from additional specific segmentation terms. It would also be interesting to evaluate our model on other WSL applications, e.g. pose estimation, key point detection, instance segmentation, dense captioning [START_REF] Johnson | DenseCap: Fully Convolutional Localization Networks for Dense Captioning[END_REF]) and visual grounding [START_REF] Fukui | Multimodal Compact Bilinear Pooling for Visual Question Answering and Visual Grounding[END_REF].

Deep Structured ConvNets Real world images generally contain multiple labels, which could correspond to different objects, scenes, actions or attributes in an image. To address this problem, our models learn independent classifiers for all categories, but they fail to explicitly exploit the label dependencies in images. Modeling the rich semantic information and their dependencies is essential for complex scene understanding. To exploit the correlations between labels, it would be interesting to combine our approach with structured models, e.g. Structured Prediction Energy Network (SPEN) [START_REF] Belanger | Structured Prediction Energy Networks[END_REF], Architectures Deep In Output Space (ADIOS) [START_REF] Cisse | ADIOS: Architectures Deep In Output Space[END_REF]. Another complementary direction to analyze complex image is to model the interactions and relative spatial relations between the entities (i.e. persons, objects) in a scene with a graphical model. We think that models reasoning over structures can bring benefits, allowing the classification of higher-level concepts built from recognition over lower-level entities.

proportion p * i . To use label proportion during learning, we add the label proportion term L p to the SyMIL objective function (Equation 3.7). The new objective function is: ∇ w s w (x i , ŷi ) -∇ w s w (x i , y i )

P (w)
The Eq. (B.10) can be rewritten in the standard formulation

D(α) = α T c - 1 2 α T Hα (B.11)
where H is a square matrix and ∀ ȳ, ȳ ∈ Y N H ȳ ȳ = g ȳ, g ȳ with

g ȳ = - 1 N N ∑ i=1
∇ w s w (x i , ŷi ) -∇ w s w (x i , y i ) (B.12) and c ȳ = 1 N ∑ N i=1 ∆(y i , ŷi ) We solve the QP problem, with an interior-point optimizer, as in (C.-N. [START_REF] Yu | Learning Structural SVMs with Latent Variables[END_REF].

N O TAT I O N

  Figure 1.1 The image annotation problem. . . . . . . . . . . . . . . . . . . . . . Figure 1.2 Challenges in image classification. . . . . . . . . . . . . . . . . . . . Figure 1.3 Examples of car images from ImageNet, PASCAL VOC 2012 and MS COCO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 1.4 Pipeline of our image representation using object detectors. . . . . Figure 1.5 Semantic pooling pipeline for image classification. . . . . . . . . . .

3Figure 3 . 1

 31 Figure 3.1 SyMIL model motivation: symmetric vs asymmetric modeling between ⊕(blue)/ (red) bags. . . . . . . . . . . . . . . . . . . . . . Figure 3.2 Illustration of the three constraints enforced during training for a positive (green) and a negative (red) bag. . . . . . . . . . . . . . . . Figure 3.3 Toy datasets generated with different α values. The blue points (resp. red) are the instances of the positive bags (resp. negative bags) Figure 3.4 Toy dataset: test accuracy with respect to α, and visualization of the selected instances during training (α = 0.5): green over positive instances (in blue), orange over negative ones (in red). . . . . . . . Figure 3.5 Accuracy performance with respect to parameter λ (logarithmic scale) on Elephant and Musk2 datasets. . . . . . . . . . . . . . . . . Figure 3.6 Visualization of predicted latent variable for negative examples on Mammal Dataset: LSVM (red) and SyMIL (blue) . . . . . . . . . . .

6 1

 6 Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Contributions and Outline . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 1

 1 Figure 1.1.: The image annotation problem. The challenge of image annotation is to find a mapping that bridges the semantic gap between raw image pixels and semantic concepts, such as objects and scene categories. (Credit Hanlin Goh)

  Figure 1.2.: Challenges in image classification. (Credit http://cs231n.github.io/)

  Figure 1.3.: Examples of car images from ImageNet, PASCAL VOC 2012 and MS COCO.

Figure 1

 1 Figure 1.4.: Pipeline of our image representation using object detectors.

Figure 1

 1 Figure 1.5.: Semantic pooling pipeline for image classification.

  Figure 2.1.: Standard deep ConvNet architectures in computer vision.

Figure 2

 2 Figure 2.2.: Illustration of MIL for image classification: x is the image and h is a region of the image.

Figure 2

 2 Figure 2.3.: Supervised learning vs MIL: in supervised learning all the examples are labeled whereas in MIL only the bags are labeled, i.e. the instance labels are unknown. The blue dotted line shows the separator learned by the classifier.

  There are several methods to embed a bag: Simple MI[START_REF] Dong | A comparison of multi-instance learning algorithms[END_REF]) maps each bag to the average of its instances, Multi-Instance Kernels[START_REF] Gärtner | Multi-Instance Kernels[END_REF] define kernels on the bags, and MIGraph and miGraph (Z.-H.[START_REF] Zhou | Multi-instance Learning by Treating Instances As non-I.I.D. Samples[END_REF]) map a bag to an undirected graph and design a graph kernel. Distance-based methods use distance metrics to classify bags. For example, Citation k-NN (J.[START_REF] Wang | Solving the Multiple-Instance Problem: A Lazy Learning Approach[END_REF] defines a bag-to-bag distance, and uses a k-NN approach to predict bag labels. M-C2B (H.[START_REF] Wang | Robust and discriminative distance for multi-instance learning[END_REF]) learns a robust and discriminative class-to-bag (C2B) distance for MIL, where each class is a "super-bag" that includes all the instances in the bags of the same class.

  Figure 2.4.: Comparison of standard MIL models. The blue dotted lines show the hyperplanes learned by the models, and the blue circles show the instances used during training to find them.

Figure 2 . 5 .:

 25 Figure 2.5.: Example of semantic segmentation mask (right) and the original image (left).The color of a pixel represent its category. The data is taken from the ADE20K dataset (http://groups.csail.mit.edu/vision/datasets/ADE20K/).

  In this section, we present deep ConvNet architectures that use WSL methods to learn spatially invariant representations with image-level labels only. A well-known model is the Spatial Transformer Network (STN) (Jaderberg et al. 2015), that learns spatial transformation from data in a deep learning framework. It warps the feature map via a global parametric transformation such as affine transformation. Unfortunately, STN fails to learn the parameters of the transformation on complex images with cluttered background. Recently, several deep ConvNet architectures have been proposed to learn localized features for object localization or semantic segmentation with image-level labels only. We assume that we have a feature extraction network that generates feature maps (Figure 2.6). As we only have image-level labels during training, we use a classification loss to learn the model parameters. The challenging problem is how to transform the features maps into one score per class to use a classification loss (Figure 2.6).

Figure 2

 2 Figure 2.6.: Deep ConvNet architecture for WSL with image classification labels. The d feature maps (spatial resolution h × w) of the feature extraction network are aggregated to generate one score per class, where C is the number of classes.

Figure 2

 2 Figure 2.7.: Cascade architecture for WSL localization. (Credit (Diba, V. Sharma, et al. 2016)).

  Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 3

 3 Figure 3.1.: SyMIL model motivation: symmetric (right) vs asymmetric (left) modeling between bison ⊕ (green) / lama (red) bags. Asymmetric model seeks discriminative regions for positive bags only, whereas symmetric model seeks discriminative regions for both positive and negative bags. We show the hyperplane in black and the selected instances for each bag in dotted lines.

  Figure 3.2.: Illustration of the three constraints enforced during training for a positive (green) and a negative (red) bag. Dashed lines represent the safety margin of 1. ∆ = w, Φ(x, h + ) + Φ(x, h -) .

Figure 3

 3 Figure 3.3.: Toy datasets generated with different α values. The blue points (resp. red) are the instances of the positive bags (resp. negative bags)

Figure 3 . 5 .

 35 Figure 3.5.: Accuracy performance with respect to parameter λ (logarithmic scale) on Elephant and Musk2 datasets.

Figure 3

 3 Figure 3.6.: Visualization of predicted latent variable for negative examples on Mammal Dataset: LSVM (red) and SyMIL (blue)

Figure 4

 4 Figure 4.1.: MANTRA prediction maps for library classifier s l a) and cloister classifier s c 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.

Figure 4 Figure 4

 44 Figure 4.2.: Multi-class accuracy (%) with respect to the scale.

  Figure 4.4.: Example of response map for UIUC-Sports images and for model of the correct class (left column) and models of incorrect class. For each model, the red (resp. blue) bounding box show the region with the maximum (resp. minimum) score.

Figure 4

 4 Figure 4.7.: Analysis of hyper-parameter C on ranking performances.

Figure 5 .

 5 Figure 5.1.: WELDON architecture is decomposed into two sub-networks: a feature extraction network (left) and a prediction network (right). The feature extraction network is based on VGG16 to extract local features from whole images with good spatial resolution. Then a transfer layer is used to learn class-specific heatmaps (car, boat), and finally a prediction layer aggregates the heatmaps to produce a single score for each class. The dot line shows the feature map size for the standard image size 224 × 224.

  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 k -lowest-instances instead of the min, with k -= 3. d) Learning the deep WSL with ranking loss, e.g. AP, in the concerned datasets (PASCAL VOC).

Figure 5 .

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

  In addition to the new spatial pooling, our model Weakly supervIsed Learning of Deep Convolutional neurAl neTwork (WILDCAT) extends WELDON model at two other levels. As spatial resolution is crucial for localization, we propose a new Fully Convolutional Network (FCN) architecture based on ResNet-101 (He et al. 2016) to learn feature maps with more resolution than WELDON model. The second novelty, which is the main one, is the introduction of a multi-map transfer stage to enrich the class model. While the WELDON model learns one modality per class, the WILDCAT model explicitly learns multiple localized features related to complementary class modalities in a WSL fashion. In Figure 6.1, we show the heatmaps of two modalities of the dog class: the first modality (b) focuses on the head, while the second modality (c) focuses on the legs of the dog. These modalities allow to focus on specific parts of objects to have a more discriminative model. The WILDCAT model can be used to perform image classification as well as weakly supervised pointwise object localization and segmentation (Figure 6.1 (d)).

  Figure 6.1.: WILDCAT example performing localization and segmentation (d), based on different class-specific modalities, here head (b) and legs (c) for the dog class.

Figure 6 .

 6 Figure 6.2.: WILDCAT architecture. The first map of dog (resp. cat) category mostly focuses on the head of the dog (resp. cat) whereas the second map focuses on the legs of the dog (resp. cat).

Figure 6 .

 6 Figure 6.3.: WILDCAT local feature encoding and pooling. Class modalities are encoded with a multi-map WSL transfer layer and pooled separately for all classes. Local features are then aggregated with a global spatial pooling to yield a single score per class.

  Figure 6.4.: Network architecture comparison

  on all three datasets, e.g. 1.7 pt on VOC 2007. Note that the strategy of architecture (a) has a very different interpretation from (b): (a) classifies each region independently and then pools the region scores, whereas (b) pools the output of the convolution maps and then performs image classification on the pooled space

Figure 6 .

 6 Figure 6.5.: Analysis of parameter α.

Figure 6 . 6 .:

 66 Figure 6.6.: Classification and localization performances with respect to α on VOC 2012.

  Figure 6.7.: Segmentation examples on VOC 2012. Our prediction is correct except for the train (last row) where our model aggregated rails and train regions. For objects as bird or plane, one can see how two heatmaps (heatmap1 (c) and heatmap2 (d) representing the same class: respectively bird, aeroplane, dog and train) succeed to focus on different but relevant parts of

Figure 6 .

 6 Figure 6.8.: Pooling analysis. We compare different spatial pooling strategies on 6 datasets for an input image of size 448 × 448.

∇∇

  i , ŷi ) + s w (x i , ŷi )s w (x i , y i )where α ≥ 0 and ∀ ȳ = ( ŷ1 , . . . , ŷN ) ∈ Y N , α ȳ ≥ 0. Then, we differentiate the constraints with respect to the primal variables:∇ w L(w, ξ, α) = w + ∑ s w (x i , ŷi ) -∇ w s w (x i , y i )) = 0 (B.2)The equation of w with dual variables is: w s w (x i , ŷi ) -∇ w s w (x i , y i ) a condition on the sum of dual variables:0 ≤ ∑ ȳ∈Y N α ȳ ≤ C (B.5) Dual formulation Applying the Equation B.3,Equation B.4, in the Lagrangian (Equation B.1), the dual formulation of the optimization problem (Equation 4.10) is ,y i ) + s w (x i , ŷi )s w (x i , y i ) w s w (x i , ŷi ) -∇ w s w (x i , y i ) , y i ) + s w (x i , ŷi )s w (x i , y i ) w s w (x i , ŷi ) -∇ w s w (x i , y i ) ŷi , y i ) + w, ∇ w s w (x i , ŷi) -∇ w s w (x i , y i ) ) w s w (x i , ŷi ) -∇ w s w (x i , y i )

  N set of negative examples D = {(x i , y i )} N i=1 training set with N examples L(y , y) loss L : Y × Y → R R regularizer [x] + = max(0, x) hinge loss -Union i.i.d.independent and identically distributed

  Figure 2.1 Standard deep ConvNet architectures in computer vision. . . . . . Figure 2.2 Illustration of MIL for image classification: x is the image and h is a region of the image. . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 2.3 Supervised learning vs MIL . . . . . . . . . . . . . . . . . . . . . . . Figure 2.4 Comparison of standard MIL models. . . . . . . . . . . . . . . . . . . Figure 2.5 Example of semantic segmentation mask (right) and the original image (left). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 2.6 Deep ConvNet architecture for WSL with image classification labels. Figure 2.7 Cascade architecture for WSL localization. . . . . . . . . . . . . . .

Table 2 . 1

 21 Details of the notations used in this thesis. For image classification, x is the image, y is the label and h is a region of the image. . . . . Table 2.2 Comparison of pooling strategies for output and latent variables with the unified framework (Equation 2.16). . . . . . . . . . . . . . Table 2.3 Dataset information: number of train and test images, number of classes and evaluation measures. . . . . . . . . . . . . . . . . . . . . 3 symil: minmax latent svm for weakly labeled data 31 Table 3.1 Classification performances (accuracy) on Mammal dataset . . . . Table 3.2 Instance selection for text classification. . . . . . . . . . . . . . . . . Table 3.3 Dataset Statistics. The features of text datasets are sparses. . . . . .

Table 3.4 Bag classification accuracy (%) on the three datasets. Boldfaced numbers indicate best results. . . . . . . . . . . . . . . . . . . . . . . Table 3.5 Classification performances on Mammal dataset . . . . . . . . . . . Table 3.6 Classification and localization performances on PASCAL VOC 2007. Table 3.7 Detection performances on Mammal dataset (Ov. = overlap) . . . . 4 mantra: minimum maximum latent structural svm 51 Table 4.1 Number of regions per image for each scale. . . . . . . . . . . . . . Table 4.2 Performances comparison and training time between MANTRA and LSSVM for scale 30% . . . . . . . . . . . . . . . . . . . . . . . . . Table 4.3 MANTRA results and comparison to state-of-the art works . . . . Table 4.4 Ranking and detection results on VOC 2011 Action. . . . . . . . . . Table 4.5 Ranking performances on PASCAL VOC 2007. . . . . . . . . . . . . 5 weldon: negative evidence for wsl of deep structured models

Table 5 . 1

 51 Proposed multi-scale ConvNet feature extraction networks. . . . .Table 5.2 Systematic evaluation of our Weakly Supervised Learning (WSL) deep ConvNet contributions on object and context datasets (MAP evaluation). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table 5.3 Systematic evaluation of our WSL deep ConvNet contributions on scene datasets (multi-class accuracy). . . . . . . . . . . . . . . . . . Table 5.4 MAP results on object recognition datasets. WELDON and state-ofthe-art methods results are reported. . . . . . . . . . . . . . . . . . .

Table 5 . 5

 55 Multiclass accuracy results on scene categorization datasets. WEL-

DON and state-of-the-art methods results are reported. . . . . . . . Table 5.6 WELDON results and comparison to state-of-the-art methods on context datasets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  .10 Comparison of weakly supervised semantic segmentation methods on VOC 2012. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table 6.11 Model comparison with corresponding parameters. . . . . . . . . . Table A.1 Results on image and molecule datasets for SyMIL and SyMIL+label proportion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table A.2 Results on Text datasets for SyMIL and SyMIL+label proportion .

  DiscussionThe methods based on bounding box supervision or object detectors previously presented give better performances than standard classification models based on global representations. This also validates that localized representations are relevant for image classification. Training object detectors requires bounding box annotations, which are not available in the standard image classification setting. The bounding box annotation gives information about the size and the location of the object, whereas imagelevel annotation only indicates if at least one object is present. Moreover, the annotation process for object bounding boxes is usually resource intensive and difficult to scale up

  Chapter 3 introduces a new model SyMIL for binary bag classification, based on a symmetric pooling. Unlike Multiple-Instance Learning (MIL) approaches, the SyMIL model seeks discriminative instances in both positive and negative bags. We validate our SyMIL model on different kind of data: image, text and molecule.

  Chapter 6 extends the work presented in Chapter 5, this time focusing on the network architecture and the spatial pooling. We propose a new multi-map transfer to learn several modalities per class, and a new spatial pooling function, which generalizes the WELDON pooling of Chapter 5. The content of this chapter is based on (Durand et al. 2017), which is a joint work with Taylor Mordan. Before presenting our contributions, we provide relevant background for both image representation with deep ConvNets and WSL in Chapter 2. In Chapter 7, we finally summarize our contributions and suggest directions for future work. Visual Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . Learned

		C h a p t e r	2
	R E L AT E D W O R K
	Contents
	2.1 9
	2.1.1	Handcrafted Representation: Bag of Words . . . . . . . . . . . . 10
	2.1.2

Representation: Deep ConvNets . . . . . . . . . . . . . 11 2.2 Weakly Supervised Learning . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2.1 Multiple-Instance Learning & its Extensions . . . . . . . . . . . 17 2.2.2 Weakly Supervised Learning with Structured Output . . . . . . 21 2.3 Weakly Supervised Learning of Deep ConvNets . . . . . . . . . . . . . 26 2.4 Image Classification Datasets . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.5 Summary & Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

  To optimally perform domain adaptation in this context, it becomes necessary to align informative image regions. To achieve region alignment, several methods use richer annotations (e.g. bounding boxes annotations[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] N. Zhang et al. 2014), segmentation masks

Table 2 .

 2 2.: Comparison of pooling strategies for output and latent variables with the unified framework (Equation 2.16).than maximizing. This MSSVM objective is similar to LSSVM objective (Equation2.10), except replacing the max operator of h (max h g(y, h) where g is a function of both y and h) with the Log-Sum-Exp (LSE) function (log ∑

h exp g(y, h)). On the contrary, Multinomial Latent Logistic Regression (MLLR) (Z.

Xu et al. 2014

) marginalizes over the output variables and maximizes over the latent variables. Another popular model for structured output prediction with latent variables is the Hidden Conditional Random Field (HCRF)

(Quattoni, S. B. Wang, et al. 2007)

, which naturally extends the Conditional Random Field (CRF)

[START_REF] Lafferty | Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data[END_REF]

to include hidden variables. Unlike MSSVM which marginalizes only over the latent variables, the HCRF marginalizes over both output and latent variables. The max operator of y in the MSSVM objective function is replaced by the LSE function. To control the uncertainty in the HCRF model, the -framework

[START_REF] Pletscher | Entropy and Margin Maximization for Structured Output Learning[END_REF][START_REF] Schwing | Efficient Structured Prediction with Latent Variables for General Graphical Models[END_REF]

) introduces a temperature parameter > 0, by replacing log ∑ y,h exp g(y, h) with log ∑ y,h exp g

  [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF]) is a popular large scale dataset which contains 1.2M training images and 1,000 categories. Unlike PASCAL VOC and MS COCO, there is a single label per image.• Scene categorization. The 15 Scene dataset[START_REF] Lazebnik | Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories[END_REF] is a single-label image classification dataset, which contains fifteen natural scene categories: office, kitchen, living room, bedroom, store, industrial, tall building, inside cite, street, highway, coast, open country, mountain, forest, and suburb. The MIT67 (Quattoni and Torralba 2009) is a standard dataset for indoor scene classification, with 67 categories. As in 15 Scene dataset, each image has a single label. • Action recognition. The UIUC-Sports (L.-J. Li and F.-F. Li 2007) is a single-label image classification dataset which contains eight sport event categories: rowing, badminton, polo, bocce, snowboarding, croquet, sailing, and rock climbing. The PASCAL VOC

are standard benchmarks for object recognition, and contain twenty classes: aeroplane,

bicycle, bird, boat, bottle, bus, car, cat, chair, cow, dining table, dog, horse, motorbike, person, potted plant, sheep, sofa, train

and TV/monitor. Each image is a realistic scene (i.e. non-iconic image) from Flickr and can contained several objects. The Microsoft Common Objects in Context (MS COCO) (T.-Y.

[START_REF] Lin | Microsoft COCO: Common Objects in Context[END_REF]

) is similar to PASCAL VOC but contains more classes (80) and considerably more object instances per image. The ImageNet Large Scale Visual Recognition Challenge (ILSVRC) dataset

[START_REF] Russakovsky | Object-centric spatial pooling for image classification[END_REF] Action (Everingham, Van Gool, et al. 2012

) contains ten categories: jumping, phoning, playing a musical instrument, reading, riding a bicycle or motorcycle, riding a horse, running, taking a photograph, using a computer, and walking. The VOC 2012 Action classification task is harder than UIUC-Sports, because the actions are not mutually exclusive, e.g. a person may simultaneously be walking and phoning.

• Fine-grained recognition. The People Playing Musical Instrument (PPMI) dataset

[START_REF] Yao | Grouplet: A Structured Image Representation for Recognizing Human and Object Interactions[END_REF]

) contains images of humans interacting with twelve different musical instruments: bassoon, cello, clarinet, erhu, flute, French horn, guitar, harp, recorder, saxophone, trumpet, and violin. For each instrument, there are images that contain a person playing the instrument, as well as images that contain a person holding the instrument without playing. Caltech-UCSD Birds 200 (CUB-200) dataset

[START_REF] Wah | The Caltech-UCSD Birds-200-2011 Dataset[END_REF]

) is an image dataset with photos of 200 bird species, and each image contains a single species.

Table 2

 2

	2.5 summary & discussion

.3.: Dataset information: number of train and test images, number of classes and evaluation measures. excellent performances, standard ConvNet architectures only carry limited invariance properties: although a small amount of shift invariance is built into the models through pooling layers, strong invariance is generally not dealt with. To overcome this limitation, we propose in this thesis to use Weakly Supervised Learning (WSL) models to explicitly align image regions to be robust to strong variations.

  3.2 SyMIL Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Examples are represented as bags of instances, but we depart from standard MIL assumptions by introducing a symmetric strategy (SyMIL) that models positive and negative bags in a symmetric manner. SyMIL is represented with a latent variable model seeking the most discriminative instances. We derive a large margin formulation of our problem, which is cast as a Difference of Convex functions (DC), and optimized using the Concave-Convex Procedure (CCCP). Finally, we evaluate our model on text, musk and image MIL datasets and we analyze the selected instances for two applications.

	The work in this chapter is under review:

3.2.1 Prediction Function . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Solving the Optimization Problem . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Difference of Convex Functions . . . . . . . . . . . . . . . . . . . 3.3.2 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Toy Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2 Standard MIL Dataset Results . . . . . . . . . . . . . . . . . . . 3.4.3 Weakly Supervised Object Detection . . . . . . . . . . . . . . . . 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapter abstract

This chapter proposes a new Multiple-Instance Learning (MIL) framework for bag classification.

• Thibaut

Durand, Nicolas Thome, and Matthieu Cord (2017b)

. "SyMIL: MinMax Latent SVM for Weakly Labeled Data". In: IEEE Transactions on Neural Networks and Learning Systems (TNNLS)

[Submission]

  for training SyMIL with CCCP Input: training set {(x i , y i )} i=1,...,n 1: Set t = 0, randomly initialize {h + i,0 , h - i,0 } i=1,...,n and linearize the concave part 2: repeat

	3:	Solve convex problem
		w t+1 = arg min w	P CCCP t	(w)	or	α t+1 = arg max α	D CCCP t	(α)	(3.14)
	4:	t ← t + 1
	5:

, this solution offers the possibility to jointly optimize some latent variables with the classifier parameters for each convex sub-problem, resulting in different (and better) local Algorithm 3.1

  6 with three different applications: molecule categorization, automatic image annotation, and text categorization. We start by giving details of datasets: http://kdd.ics.uci.edu/databases/reuters21578/reuters21578.html http://wordnet.princeton.edu The datasets are available at http://www.cs.columbia.edu/andrews/mil/datasets.html

		LSVM	SyMIL
	a) Predictive accuracy
		96.3%	97.6%
	b) Similarity between instances and category
		Bag ⊕ = 74%	Bag = 67%	Bag ⊕ = 73%	Bag = 78%
	c) Examples
	Bag ⊕ bank, currency, money, exchange, treasury bank, exchange, rate, currency, monetary
	Bag	west, finance, bank, british, money	oil, opec, shipping, port, union

Table 3 .

 3 2.: Instance selection for text classification: a) predictive accuracy b) words in selected instances which are a semantically correlated to the category and c) example of top 5 selected words. The positive (resp. negative) bags are texts of the category money (resp. categories ship and crude).

Table 3 .

 3 3 provides information about the number of training examples, the average number of instances per bag for each dataset, and the dimension of the features.

	Dataset	Image	Musk1 Musk 2	Text
	pos/neg bags	100/100 47/45	39/63	200/200
	instances/bag	∼ 6.5	5.17	64.69	∼ 8
	feature dimension	230	166	166	∼ 66 500

Table 3 .

 3 3.: Dataset Statistics. The features of text datasets are sparses.

Table 3

 3 The overall results for the three kind of datasets (image, text, molecule) are gathered in Table3.4. A first comparison is given in Table3.4 a) with methods the most closely connected to ours: mi-SVM/MI-SVM[START_REF] B I B L I O G R A P H Y Andrews | Support Vector Machines for Multiple-Instance Learning[END_REF] and LSVM

	a) Re-implemented method
	mi-SVM	73.4	84.5	81.6
	MI-SVM	75.5	81.7	80.3
	LSVM	74.4	82.7	80.0
	SyMIL linear	79.1	88.2	84.8
	RBF	80.2	89.2	-
	Without constraints 1 & 2 linear	78.1	86.9	83.7
	RBF	78.7	87.5	-
	b) State-of-the art results
	SyMIL	80.2	89.2	84.8 84.7
	mi-SVM (Andrews et al. 2003)	72.9	85.5	81.6 80.0
	MI-SVM (Andrews et al. 2003)	74.4	81.1	81.4 79.0
	ALP-SVM (Gehler et al. 2007)	77.9	86.3	-	-
	MICA (Mangasarian et al. 2008)	73.9	87.5	82.3 80.1
	MIGraph (Z.-H. Zhou et al. 2009)	76.1	90.0	-	-
	MiGraph (Z.-H. Zhou et al. 2009)	78.1	89.6	-	-
	MI-CRF (Deselaers et al. 2010)	78.5	86.7	-	-
	Convex relaxation (Joulin et al. 2012)	75.8	-	-	-
	GP-WDA (Kim et al. 2013)	79.0	88.4	83.2 83.5
	eMIL (Krummenacher et al. 2013)	77.0	85.3	82.7 81.7
	MILEAGE (D. Zhang et al. 2013)	77.7	-	-	-

.4.: Bag classification accuracy (%) on the three datasets. Boldfaced numbers indicate best results.

the standard protocol to evaluate performances, as described in

[START_REF] B I B L I O G R A P H Y Andrews | Support Vector Machines for Multiple-Instance Learning[END_REF]

: the performances are evaluated using a 10-times 10-fold cross-validation.

Table 3

 3 Table 3.5.: Classification performances on Mammal datasetThe results are reported in Table3.5. As we can see, our SyMIL model outperforms other approaches using both metrics. The trend is the same for both metrics (MAP & accuracy). In addition, all improvements are statistically significant (risk 5%). The prediction results again illustrate the superiority of the symmetric modeling, especially with respect to

	MAP (%) Accuracy (%)

.7.: Detection performances on Mammal dataset (Ov. = overlap) Kernel Latent SVM (KLSVM) (W.

[START_REF] Yang | Kernel Latent SVM for Visual Recognition[END_REF]

where the comparison directly measures the impact of the min/max selection strategy. Our method also has an edge over M3E, which tackles the weakly supervised learning in a direction complementary to ours (modeling ambiguities between latent variables).

PASCAL VOC 2007

We perform another experiment on the PASCAL VOC 2007 dataset, presented in Section 2.4. For each image, we extract 25 regions of size 60% (of the image size) with a sliding window strategy. To have a vectorial representation of each region, we extract deep features pre-trained on ImageNet using MatConvNet library (A.

[START_REF] Vedaldi | MatConvNet -Convolutional Neural Networks for MATLAB[END_REF]Vedaldi et al. ) (model vgg-m-2048))

. Each region is represented by a 2048-dimensional vector (output of the FC7 layer after the ReLU).

  Training set {(x i , y i )} i=1,...,N , precision ε, C. Initialize t ← 1, { ŷi , h + i, ŷi , h - i, ŷi } i=1,...,N and compute initial cutting plane (g 1 , c 1 )

	2: repeat 3: // Update working set and solve QP g Algorithm 4.1 Cutting Plane Algorithm for training MANTRA 4:	y )	(4.12)

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

(Do et al. 2012)

. The algorithm stops as soon as no constraint can be found that is violated by more than the desired precision ε (Line 16).

Input:

1:

  Table 4.1.: Number of regions per image for each scale.

	Scale	90 80 70 60 50 40 30
	Number of regions	4	9 16 25 36 49 64
			31)

  The Figure4.3 shows the training time required on 1 CPU (2.7 Ghz, 32 Go RAM) to train models on UIUC-Sports, 15 Scene, PPMI and MIT67. 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 about 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 4.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 1-slack cutting plane strategy to solve the optimization problem (Subsection 4.2.3) is efficient.Comparison to LSSVM As previously mentioned, most of state-of-the-art WSL works are based on Deformable Part Model (DPM)[START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF] or LSSVM (C.-N.[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 Table4.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 Table4.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

Table 4 .

 4 2.: Performances comparison and training time between MANTRA and LSSVM for scale 30%. MANTRA-C is MANTRA with CCCP, and LSSVM-N is LSSVM with NCCP.

	Method	UIUC	15 Scene PPMI MIT67
	Multi-class accuracy (%)
	LSSVM	73.3 ± 0.3 65 ± 1.5	13.3	26.6
	MANTRA	93.2 ± 1.0 80.7 ± 0.7 51.0	56.4
	LSSVM-N	71.6 ± 1.3 64.3 ± 0.9 13.6	25.2
	MANTRA-C 93.2 ± 0.9 80.4 ± 0.6 50.9	56.5
	Average training time (seconds)
	LSSVM	1863	14179	21327 156360
	MANTRA	61	843	2593	41805

Table 4

 4 Example of response map for 15 Scene images and for model of the correct class (left column) and models of incorrect class. For each model, the red (resp. blue) bounding box show the region with the maximum (resp. minimum) score.

	Model of GT class		Models of incorrect class
	coast	forest	open country	street
	street	highway	inside city	open country
	highway	forest	open country	street
	tall building	coast	inside city	office
	Figure 4.6.:

.3.: MANTRA results and comparison to state-of-the art works ( † is our reimplementation).

  Table 4.4.: Ranking and detection results on VOC 2011 Action.

		MAP (%)	Detection overlap (%)
	LSSVM-Acc	29.5 ± 1.3	12.7 ± 0.3
	MANTRA-Acc	35.2 ± 1.2	18.9 ± 0.9
	LAPSVM	36.7 ± 0.8	20.1 ± 0.7
	MANTRA-AP	42.2 ± 1.3	26.5 ± 1.4

  Table 4.5.: Ranking performances on PASCAL VOC 2007.

		MAP (%)
	Deep transfer (Oquab et al. 2014)	77.7
	SPP-net (He et al. 2014)	80.1
	vgg-m-2048 (Chatfield et al. 2014)	82.4
	MANTRA-Acc	82.6
	MANTRA-AP	85.8

Table 5 .

 5 Image size I Region scale α (%) conv5 output size conv6 output size 1.: Proposed multi-scale ConvNet feature extraction networks. Input images are rescale to I × I images, with I in the range [224, 747]. At each scale, regions span 224 × 224 areas, so that the region scale is α = 224/I.

	224 × 224	100	7 × 7	1 × 1
	249 × 249	90	8 × 8	2 × 2
	280 × 280	80	9 × 9	3 × 3
	320 × 320	70	10 × 10	4 × 4
	374 × 374	60	12 × 12	6 × 6
	448 × 448	50	14 × 14	8 × 8
	560 × 560	40	18 × 18	12 × 12
	747 × 747	30	24 × 24	18 × 18

  1 . We evaluate our WELDON model on several computer vision benchmarks corresponding to various visual recognition tasks. Contrary to MANTRA experiments (Section 4.4) where we choose pre-trained deep features according to the target task, we use only deep features pre-trained on ImageNet whatever the visual recognition task to highlight the generality of our model. We evaluate our model in different recognition contexts: object recognition (PASCAL VOC 2007, PASCAL VOC 2012), scene categorization (MIT67 and 15 Scene), and visual recognition, where context plays an important role (MS COCO, PASCAL VOC 2012 Action)

Table 5 .

 5 a) max b) +top c) +min d) +AP VOC 2007 VOC 2012 Action 3.: Systematic evaluation of our WSL deep ConvNet contributions on scene datasets (multi-class accuracy).

	83.6	53.5
	86.3	62.6
	87.5	68.4
	88.4	71.7
	87.8	69.8
	88.9	72.6

Table 5

 5 .5 and Table5.6).

	Method	VOC 2007 VOC 2012 (val)
	Return Devil (Chatfield et al. 2014)	82.4	-
	VGG16 (Simonyan et al. 2015)	84.5	82.8
	SPP-net (He et al. 2014)	82.4	-
	Deep MIL (Oquab et al. 2015)	-	81.8
	MANTRA (Chapter 4)	85.8	-
	WELDON	90.2	88.5

Table 5 .

 5 4.: MAP results on object recognition datasets. WELDON and state-of-the-art methods results are reported.

Table 5 .

 5 and MANTRA. As observed in Subsection 5.5.1, we note that our multi-regions pooling strategy significantly outperforms max (Deep MIL) and max+min (MANTRA) pooling. This big improvement illustrates the positive impact of incorporating MIL relaxations for WSL training of deep ConvNets, i.e. negative evidence scoring and topinstance selection. Finally, we can point out the outstanding score reached by WELDON on VOC 2007, exceeding the nominal score of 90%. 5.: Multiclass accuracy results on scene categorization datasets. WELDON and state-of-the-art methods results are reported.

	Method

Table 5 .

 5 this chapter, we introduced a novel framework for WEakly supervised Learning of Deep cOnvolutional neural Network (WELDON). WELDON is trained to automatically 6.: WELDON results and comparison to state-of-the-art methods on context datasets.select relevant regions from images annotated with global labels, and to perform endto-end learning of a deep ConvNet from the selected regions. The whole architecture is carefully designed for fast processing by sharing region feature computations, and for robust training. We also proposed a new pooling function, which generalizes the MANTRA pooling function by incorporating top instance strategy.

	Method	VOC 2012 Action MS COCO
	VGG16 (Simonyan et al. 2015)	67.1	59.7
	Deep MIL (Oquab et al. 2015)	-	62.8
	WELDON	75.0	68.8

  (x, y, h) is the score for category y at location h (after class-wise pooling), Cl. Pool is the chosen class-wise pooling function and Sp. Pool is the spatial aggregation process.

				.1)
	where F t w (x, y, h) = Cl. Pool m∈{1,...,M}	F multi w	(x, (y, m), h)	(6.2)
	where F t w

Table 6 .

 6 1.: Generalization of wildcat spatial pooling to other existing MIL approaches with corresponding parameters. n is the total number of regions, ρ is the proportion of positive labels in LLP, k is an arbitrary number of regions to choose.Several similar MIL approaches have been used but our proposed model generalizes them in numerous of ways. The corresponding parameters are described in Table6.1. The standard max-pooling MIL approach[START_REF] Oquab | Is object localization for free? -Weakly-supervised learning with convolutional neural networks[END_REF] is obtained with only one element, and both top instance model (W.[START_REF] Li | Multiple Instance Learning for Soft Bags via Top Instances[END_REF], Learning with Label Proportion (LLP) (F. X.[START_REF] Yu | ∝SVM for Learning with Label Proportions[END_REF] and global average pooling

	Pooling	k + k -α
	Maximum / MIL (Oquab et al. 2015)	1	0 0
	Top instances (W. Li et al. 2015)	k	0 0
	LLP (F. X. Yu et al. 2013)	ρn 0 0
	GAP (Bolei Zhou, Khosla, et al. 2016) n	0 0
	MANTRA (Chapter 4)	1	1 1
	WELDON (Chapter 5)	k	k 1

•

  Combining α = 0.7 and M = 4 improvements further boost performances: 0.4 pt on VOC 2007, 0.8 pt on VOC 2012 Action and 0.8 on MIT67. This shows the complementarity of both these contributions. Table 6.4.: Ablation study on VOC 2007, VOC 2012 Action and MIT67. The results are different from results of Subsection 6.3.2 because only one scale is used for this analysis.6.3.2 Comparison with State-of-the-Art MethodsFirstly, we compare the proposed WILDCAT model to state-of-the-art methods. We use different image size as input of our model, and scale combination is performed using an Object-Bank (L.-J.[START_REF] Li | Object Bank: An Object-Level Image Representation for High-Level Visual Recognition[END_REF] strategy. The image size and the values of k + /k -are given in Table6.5. The hyper-parameters of our model are fixed at M = 4 and α = 0.7. An analysis of the number of selected regions is done in Subsection 6.5.2, showing further improvements by careful tuning. Results are gathered in Table6.6 and Table6.7.

	max+min α = 0.7 M = 4 VOC 2007 VOC 2012 Action MIT67
		89.0	78.9	69.6
		90.3	80.9	71.3
		91.6	82.1	72.0
		92.0	82.9	72.8
	Image size Size before pooling k + , k -
	224 × 224	7 × 7	3
	280 × 280	9 × 9	5
	320 × 320	10 × 10	10
	374 × 374	12 × 12	15
	448 × 448	14 × 14	20
	560 × 560	18 × 18	25
	747 × 747	24 × 24	30

Table 6 .

 6 5.: Multi-scale setup for WILDCAT model. We detail the input image sizes, along with the sizes of the feature maps before spatial pooling and the parameter values used in the spatial pooling.Object datasets We report in Table6.6 the performances for object datasets, and we can see that WILDCAT outperforms all recent methods based on deep features by a large margin. The most important comparison is the improvement over other recent

	Method	VOC 2007 VOC 2012 MS COCO
	Return Devil (Chatfield et al. 2014)	82.4	-	-
	VGG16 (Simonyan et al. 2015)	89.3	89.0	-
	SPP-net (He et al. 2014)	82.4	-	-
	NUS-HCP (Y. Wei et al. 2014)	85.2	84.2	-
	ResNet-101 (He et al. 2016) †	89.8	89.2	72.5
	Deep MIL (Oquab et al. 2015)	-	86.3	62.8
	MANTRA (Chapter 4)	85.8	-	-
	WELDON (Chapter 5)	90.2	-	68.8
	ProNet (C. Sun et al. 2016)	-	89.3	70.9
	RRSVM (Z. Wei et al. 2016)	92.9	-	-
	SPLeaP (Kulkarni, Jurie, et al. 2016)	88.0	-	-
	WILDCAT	95.0	93.4	80.7

WSL methods on deep features

[START_REF] Oquab | Is object localization for free? -Weakly-supervised learning with convolutional neural networks[END_REF] C. Sun et al. 2016;[START_REF] Rrsvm | GoogleNet-GAP[END_REF]

, MANTRA, WELDON. We outperform the deep WSL ConvNet 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 7.1 pt (resp. 17.9) on VOC 2012

Table 6 .

 6 6.: MAP results on object recognition datasets. WILDCAT and state-of-the-art methods results are reported. Half at the top shows the performances using global image representation, whereas the half at the bottom shows performances for models based on regions selection. † means that the results are obtained by fine-tuning the network on the dataset with the code https://github.com/facebook/fb.resnet.torch.(resp. MS COCO). This big improvement illustrates the positive impact of incorporating MIL relaxations for WSL training of deep ConvNets, i.e. negative evidence scoring and top-instance selection. We also note a significant gain of 4.1 pt (resp 9.8) on VOC 2012 (resp. MS COCO) with ProNet (C.Sun et al. 2016), that relaxes the max pooling with a LSE pooling. WILDCAT also outperforms by 2.1 pt the RRSVM (Z.[START_REF] Wei | Region Ranking SVM for Image Classification[END_REF] on VOC 2007, which learn a constrained aggregation operator on all the regions. Compared to WELDON, the improvement of 4.8 pt (resp. 11.9) on VOC 2007 (resp. MS COCO) essentially shows the importance of the ResNet-101 that preserves spatial information throughout the network, and allows finer maps to learn more specific regions.Scene, action and fine-grained datasetsWe also validate our model on scene, action and fine-grained classification. The results are reported in Table6.7 and illustrate the big improvement of WILDCAT compared to deep features computed on the whole image (B.[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][START_REF] He | Deep Residual Learning for Image Recognition[END_REF]) and global image representation with deep features computed on image regions: MOP CNN[START_REF] Gong | Multi-scale Orderless Pooling of Deep Convolutional Activation Features[END_REF] and Compact Bilinear Pooling[START_REF] Gao | Compact Bilinear Pooling[END_REF]. It is worth noticing that WILDCAT also outperforms recent part-based methods[START_REF] Wu | Harvesting Discriminative Meta Objects With Deep CNN Features for Scene Classification[END_REF][START_REF] Kulkarni | SPLeaP: Soft Pooling of Learned Parts for Image Classification[END_REF] including negative evidence during training

Table 6 .

 6 by 3.2 pt (resp. 4.2 pt) on VOC 2012 (resp. MS COCO), which use a more complex strategy than our model, based on search-trees to predict locations.

	Method	VOC 2012 MS COCO
	Deep MIL (Oquab et al. 2015)	74.5	41.2
	ProNet (C. Sun et al. 2016)	77.7	46.4
	WSLocalization (Bency et al. 2016)	79.7	49.2
	WILDCAT	82.9	53.4

9.: Object localization performances (MAP) on PASCAL VOC 2012 and MS COCO.

Table 6 .

 6 10.: Comparison of weakly supervised semantic segmentation methods on VOC 2012.

	.3

  ResultsWe perform experiments on the MIL datasets presented in Subsection 3.4.2. The target proportion p i is set to 0.8 (resp. 0.2) for positive (resp. negative) bags, and ρ (sigmoid parameter) is cross-validated on the training set. Results are shown in TableA.1 & TableA.2. As we can notice, the proposed label proportion is itself competitive, since it outperforms baselines mi-SVM / MI-SVM / LSVM in all datasets (see Table3.4), but remains below SyMIL performances. The combination SyMIL+label proportion is able to further improve SyMIL performances, especially on the image and molecule datasets. This experiment validates the complementarity potential between the two approaches. Table A.1.: Results on image and molecule datasets for SyMIL and SyMIL+label proportion Table A.2.: Results on Text datasets for SyMIL and SyMIL+label proportion

	=	1 2	w 2 + CL(w, D) +	C p N ∑ i∈D	L p ( p(x i ; w), p * i )	(A.4)
	The optimization problem (Equation A.4) is solved with a Stochastic Gradient Descent
	(SGD) strategy (Léon Bottou 2010).
	Dataset	Elephant Fox Tiger Avg. Musk1 Musk2 Avg.
	label proportion		82.4		62.5 82.1	75.7	83.5	85.6	84.6
	SyMIL		87.2		64.9 85.3	79.1	88.5	87.8	88.2
	SyMIL+label prop.		87.9		65.7 86.3	80.0	89.3	89.3	89.3
	Dataset	TST1 TST2 TST3 TST4 TST7 TST9 TST10 Avg.
	label proportion	93.8	81.1	86.1	86.0		81.7	68.9	83.9	83.0
	SyMIL	94.3	84.3	88.8	87.1		82.3	71.2	85.8	84.8
	SyMIL+label prop. 94.8	84.9	88.7	87.5		82.6	71.5	86.0	85.1

  joint feature map Ψ : X × Y × H → R d Φ(x, h) joint feature map Φ : X × H → R d P set of positive examples

	symbol	meaning
	w ∈ R d	vector of parameters (dimension d)
	f w (x)	prediction function f w : X → Y
	s w (x, y)	scoring function s w : X × Y → R
	X	input space
	x ∈ X	input variable
	Y	output space
	y ∈ Y	output variable
	y	ground truth output variable
	H	latent space
	h ∈ H	latent variable
	Ψ(x, y, h)

http://www.businessinsider.com/facebook-350-million-photos-each-day-2013-9?IR=T

https://maximizesocialbusiness.com/definitive-instagram-statistics-23286/

http://www.cisco.com/c/en/us/solutions/collateral/service-provider/ visual-networking-index-vni/vni-hyperconnectivity-wp.html

http://www.image-net.org/challenges/LSVRC/2012/

http://mscoco.org

In the SVM case, the class of functions is the set of linear separators with a bounded norm {x → w, Φ(x) : w ≤ W}, for some W > 0.

The difference with LSVM is that bag and loss functions are 1-Lipschitz.

www.mosek.com

We notice it has a small impact if it is sufficiently large.

Note that our re-implementation matches the results in reported in[START_REF] B I B L I O G R A P H Y Andrews | Support Vector Machines for Multiple-Instance Learning[END_REF].

SyMIL results are reported for RBF kernels in the image and molecules datasets, but for linear kernels in the text datasets. This is similar to the setup in[START_REF] Kim | Multiple Instance Learning via Gaussian Processes[END_REF], since linear models generally lead to better performances.

see M3E webpage.

www.mosek.com

http://torch.ch/

Chapter abstract

The SyMIL model introduced in the previous chapter is based on a pair of latent variables (h + , h -) for prediction. While the SyMIL model is limited to binary labels, we propose to extend this model to more general outputs. We instantiate our model for two different visual recognition tasks: multi-class classification and ranking. For ranking, we propose efficient solutions to exactly solve the inference and the lossaugmented problems. Finally, we validate the relevance of our model on six different datasets.

The work in this chapter has led to the publication of a conference paper:

• Thibaut [START_REF] Durand | MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking[END_REF]. "MANTRA: Minimum Maximum Latent Structural SVM for Image Classification and Ranking". In: IEEE International Conference on Computer Vision (ICCV)

We notice that the predicted latent variables are the same in the two cases. So the latent variables can be fixed independently to the value of y pn . max

When the latent variables are fixed, each example x i can be represented by Φ + -(x i ), and Θ(x, y) can be written as follow:

So s w (x, y) can be written as a supervised feature map, where the latent are fixed independently to the ranking matrix y, and each example x i is represented by

The proof of Lemma 4.1 comes from a 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 4.2 directly follows from Lemma 4.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.

Time complexity Finally, we analyze the complexity of inference and loss-augmented inference for ranking instantiation. We define h as the average number of regions per images. The inference complexity with MANTRA is O(N hd + N log N), where the first term is the complexity to infer exhaustively the latent variables and the second term is the complexity of the sort. With the algorithm proposed by [START_REF] Yue | A Support Vector Method for Optimizing Average Precision[END_REF], the complexity of loss-augmented inference for MANTRA is O(N hd + N log N + |P ||N |), where the third term is the complexity to rank negative examples.

C h a p t e r

W E L D O N : N E G AT I V E E V I D E N C E F O R W E A K LY S U P E RV I S E D L E A R N I N G O F D E E P S T R U C T U R E D M O D E L S Contents

Chapter abstract

This chapter explains how to integrate MANTRA (Chapter 4) in a deep ConvNet architecture. The core of the approach is a new pooling function which generalizes the MANTRA pooling function by selecting several instances. We introduce a specific architecture design which enables an efficient processing by sharing region feature computations, as well as an easy and effective transfer learning and finetuning. We show that our model can be trained end-to-end for different visual recognition tasks: multi-class and multi-label classification, and also structured Average Precision (AP) ranking. Finally, we evaluate classification performances of our model on six challenging datasets.

The work in this chapter has led to the publication of a conference paper:

• Thibaut [START_REF] Durand | WELDON: Weakly Supervised Learning of Deep Convolutional Neural Networks[END_REF]. This validates that our model can automatically find discriminative regions, even in the case of fine-grained classification.

Large-Scale Image Classification

We also evaluate WILDCAT on ILSVRC classification challenge [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF] to show the scalability and the efficiency of our model for large-scale image classification. Table 6.8 summarizes the classification performances of WILDCAT and existing models. To have a fair comparison between models, we only report results for single model. For our model, we use a mono-scale model with an input image size 448 × 448, and k + = k -= 50.

We can see that WILDCAT outperforms most of existing models trained using whole image (VGG16 [START_REF] Simonyan | Very Deep Convolutional Networks for Large-Scale Image Recognition[END_REF], GoogleNet (Szegedy, Liu, et al. 2015)

Table 6.11.: Model comparison with corresponding parameters. indicates that the model is not exactly equivalent to the generalized pooling function with the given parameters, but has a similar behavior.

In the next section, we provide a systematic comparison of these pooling functions to highlight their strengths and weaknesses in different contexts.

Pooling Analysis Experiments

In this section, we analysis our pooling function, and we compare it with standard pooling functions presented in Section 6.5. We report results for an input image of size 448 × 448, but similar behaviors are observed for other scales. To have fair comparison, all the experiments uses the same network (ResNet-101). We analyze the impact of the number of selected instances. We show in Figure 6.8 the performance with respect to the proportion of selected regions. We can note that the GAP (resp. MANTRA pooling) is a special case of WELDON pooling, when the proportion of selected regions is 1 (resp. →0).

Firstly, we can see that negative evidence is important, because on all dataset, MANTRA is better than max pooling. In particular, we observe a large improvement of +4.5 pt on VOC 2012 Action dataset, where the context plays an important role (Georgia [START_REF] Gkioxari | Contextual action recognition with R* CNN[END_REF]. We can also see that region selection is important: on all dataset except MIT67, the WELDON pooling with a proportion of selected instances in [0.2, 0.8] is equal or better than GAP. The WELDON pooling has similar or better results than GAP by using only 20% of regions. Using more regions (50 %) gives better results than GAP: +0.4 pt on VOC 2007, +0.3 pt on VOC 2012, +0.6 pt on VOC 2012 Action, +1.9 pt and +2.1 pt on CUB-200. On MIT67, we can see that using a large number of regions is better (≥ 80 %). This shows that a large number of regions are discriminants.

We also compare our pooling function to max and LSE pooling functions. The LSE pooling is a soft extension of max pooling. On all datasets, LSE is better than max pooling: +6 pt on CUB-200 and +5.5 on MIT67. This shows that using several regions is more C h a p t e r

C O N C L U S I O N

Summary of Contributions

In this thesis, we proposed several models to learn localized representations with imagelevel labels only. Our contributions can be summarized in three points.

Pooling The key issue of WSL is to find how to pool the region scores into image scores. To address this problem, we introduced the max+min pooling function. We first applied this pooling function on bag classification with binary labels (Chapter 3). We then generalized it for structured output prediction (Chapter 4). We showed that the minimum regions bring complementary information to max regions and explicitly model negative evidence, i.e. look for "counter evidence" for the class. To have a more robust prediction, we extended this pooling function by selecting several regions (Chapter 5). As both maximum and minimum scoring regions are important for good results, but do not bring the same kind of information, we introduced a trade-off parameter to weight the importance between both terms (Chapter 6). Finally, we performed an empirical comparison of different pooling functions used for WSL on several datasets.

Optimization Another challenging problem in machine learning is how to efficiently learn the parameters of the model. This usually reduces to solving an optimization problem. For each of our models presented in this thesis, we proposed an objective function and a solver to optimize it. For SyMIL model (Chapter 3), we provided a primal solver that scales to large datasets and a dual solver to learn non-linear models. In Chapter 4, we proposed an efficient non convex cutting plane algorithm based on the one-slack formulation to train the MANTRA model. To learn deep architectures (Chapters 5 and 6), we used the Stochastic Gradient Descent (SGD). We also need an efficient optimization method to deal with structured output prediction, because we have to solve the (loss-augmented) inference problem. We tackled the Average Precision (AP) ranking problem because it is a standard evaluation measure, and we proposed a new AP ranking instantiation (Chapter 4) and its extension (Chapter 5), for which efficient solutions are introduced to solve the inference problems. A limitation of MIL methods and SyMIL relies on the prediction function which selects a single instance, making the method sensitive to false alarm outliers. Recently, the Learning with Label Proportion (LLP) framework (Subsection 2.2.1.2) has been proposed to address this problem. Unlike MIL, in LLP the bags are labeled with the proportion of positive instances. LLP methods are appealing for solving MIL problems, because they limit the impact of instance outliers, improving robustness. In this section, we combine the local information in SyMIL and the global information from the LLP framework to learn a prediction function more robust to outliers. For a given bag x i and weight vector w, the true label proportion of positive instances is:

where 1 is the Heavyside function. It is not possible to directly optimize over the Heavyside function with gradient-based approaches. Therefore, we approximate it by a sigmoid function f ρ (x) = 1 1+exp (-ρx) . We define the estimated proportion of ⊕ instances in a bag x i as:

Note that our approximation of p is more accurate than the one used in InvCal [START_REF] Rueping | SVM Classifier Estimation from Group Probabilities[END_REF], where the sigmoid is applied to the mean score of each bag.

In standard LLP contexts, the goal is to match the estimated proportion of ⊕ instances p(x i ) to the known proportion coming from ground truth annotations p i . Therefore, a regression loss is generally used during training, e.g. using the 1 norm | p(x i )p i | (Rueping 2010; F. X. [START_REF] Yu | ∝SVM for Learning with Label Proportions[END_REF][START_REF] Lai | Video Event Detection by Inferring Temporal Instance Labels[END_REF]. When applied to MIL, such a regression loss is however questionable, since there is no clear definition of p i for each bag. Instead, we propose to enforce the proportion of ⊕ instances to be larger (resp. smaller) than a target proportion p i for a positive (resp. negative) bag. To this end, we introduce the following "hinge-like" loss:

where δ i p = p(x i )p i . The loss L p ( p(x i ; w), p * i ) penalizes the positive (resp. negative) bags which have a proportion of ⊕ instances inferior (resp. superior) to the target