Keywords: Computer vision, convolutional neural networks, deep learning, weakly supervised learning, unsupervised learning, generative adversarial networks

This thesis investigates convolutional neural networks for visual recognition. Recent convolutional neural networks have demonstrated excellent performance for a variety of recognition tasks but typically require large amounts of manually annotated training data to perform well. This data is often costly to annotate and may introduce unwanted biases. In this thesis we investigate different ways how to reduce the amount and complexity of required training supervision.

In our first contribution, we propose a transfer learning approach with a convolutional neural network for object classification. We first learn mid-level features on the large ImageNet dataset during a pre-training phase, then we use the parameters to initialize another network designed for a smaller-scale task, where less training data is available. We show, first, that the image representations can be efficiently transferred to other visual recognition tasks, and second, that these representations lead to higher performance when more data is used for pre-training. We demonstrate that the proposed approach outperforms state-of-the-art on the Pascal VOC image classification task.

In our second contribution, we investigate weakly supervised learning for object recognition. We use the fact that for classification, convolutional neural networks tend to take decisions based on the most distinctive parts of objects. This allows us to build a network that can predict the location of objects, based on a weakly annotated dataset indicating only the presence or absence of objects but not their location in images. We demonstrate that our approach improves the state-of-theart on the Pascal VOC image classification task, performing on par with methods requiring full object-level supervision.

In our third contribution, we look at possible paths for progress in unsupervised learning with neural networks. We study the recent Generative Adversarial Networks; these architectures learn distributions of images and generate new samples, but the evaluation which learned model is better than others is difficult. We propose a twosample test method for this evaluation problem, allowing us to perform a first level of model selection. We investigate possible links between Generative Adversarial Networks and concepts related to causality, and propose a two-sample test method for the task of causal discovery, outperforming the state of the art. Finally, building on a recent connection with optimal transport, we investigate what these generative algorithms are learning from unlabeled data.

Résumé

Dans cette thèse nous étudions les réseaux de neurones à convolution dans les systèmes de reconnaissance visuelle. Les réseaux de neurones à convolution récents ont d'excellentes performances pour une grande variété de tâches de reconnaissance, mais requièrent une grande quantité de données d'entraînement, annotées manuellement, pour révéler leur potentiel. Obtenir des données est une opération souvent coûteuse, et qui peut introduire des biais. Dans cette thèse nous étudions différentes manires de réduire la quantité et la compléxité de la supervision.

Notre première contribution est une méthode de transfert d'apprentissage dans les réseaux à convolution pour la classification d'image. Nous apprenons des représentations intermédiaires sur la base de données ImageNet pendant une phase de préentraînement, puis utilisons les paramètres appris pour initialiser un réseau concu pour une autre tâche avec moins de données. Nous montrons d'abord que ces représentations sont assez générales pour etre utilisées sur d'autres tâches, et meilleures lorsque le pré-entraînement est réalisé avec plus de données. Ceci nous a permis d'améliorer l'état de l'art en classification d'image sur la base de données Pascal VOC.

Notre deuxième contribution est une approche faiblement supervisé, tirant parti du fait que les réseaux à convolution prennent, pour la classification, des décisions basées sur les parties les plus informatives des objets. Ceci nous a permis de créer un système pouvant predire la localisation des objets en utilisant lors de l'entraînement, seulement l'indication de la présence ou l'absence des objets dans les images, et non leur position. Nous montrons que ce système améliore l'état de l'art en classification d'image sur Pascal VOC, avec des résultats comparables à ceux des systémes disposant de la position des objects.

Dans notre troisième contribution, nous cherchons des pistes de progression en apprentissage non-supervisé. Nous étudions l'algorithme récent des réseaux génératifs adversariaux; ces architectures apprennent des distributions d'images et génèrent de nouveaux exemples, mais l'évaluation d'un modèle appris est difficile. Nous proposons d'utiliser un test statistique pour ce problème, qui permet un premier filtrage des modèles. Nous étudions ensuite le problème de la causalité avec des réseaux génératifs, et proposons d'utiliser un test statistique pour la découverte causale. Finalement, grâce a un lien établi récemment avec les problèmes de transport optimal, nous étudions ce que ces réseaux apprennent des données dans le cas non-supervisé. 5 Acknowledgments Dear Ivan, Josef, Léon, I would like to thank you for sharing your knowledge with me. When we first met in 2013, I didn't know this would be the turning point of my life. I can not thank you enough for your patience, your efforts, your attention and your time.

I am grateful to the MSR-Inria Joint Centre and to the ERC grants LEAP and ACTIVIA for their financial support during this thesis. I would like to thank Jean and Francis for setting up the Willow and Sierra research groups. If the goal was to build a stimulating environment, then I believe you have succeeded. I would like to thank the members of the jury for taking the time to read this thesis. I hope it was an enjoyable read.

I would like to thank Victor and Mathieu for proofreading this manuscript.

I would like to thank the researchers, assistants, engineers, post-docs, PhD students and interns, who all made this time enjoyable. I will keep fond memories of our lunches, coffee breaks, drinks and deadline pizzas.

I would like to thank the IT specialists for their availability and help.

I would like to thank the communication and contract specialists; I was lucky to have my office next to yours. I would like to thank Hélène in particular for always being there when I needed to be cheered up.

I would like to thank Isabelle, Catherine and Céline for running this place smoothly.

I would like to thank my co-authors Vadim, Minsu and David for their help.

I would like to thank Christophe and Guilhem for no particular reason. I would like to thank my friends and my family for their support.

I would like to thank Gül for introducing me to İlayda. I would like to thank Jacques-Alexis and Anne Lise for all the things they taught me, and Paul for sharing both the rent and his family for many years.

7

Chapter 1 Introduction

Motivation

The amount of visual data available online, thanks to readily available phone cameras, social networks, image and video hosting services, keeps growing faster and faster.

Millions of pictures are uploaded by humans every single day. 1 The goal of visual recognition is to develop algorithms and methods able to understand the content of all the visual data surrounding us.

With people carrying powerful computers in their pockets, visual recognition has practical applications outside of research labs, in the everyday life. But while it is easy to find more information on something when we know its name thanks to Internet, what happens when we don't? Visual recognition tools give access to more knowledge, by allowing to recognize objects such as animals, plants, or buildings for example, only with pictures using tools such as Google Reverse Image Search on a smartphone.

Because it is fully automatized, visual recognition is also well-suited for security purposes. For instance, millions of hours of footage are produced daily by surveillance cameras, and there is not enough human capacity to monitor all of it and recognize sequences of interest. Similarly, automatizing baggage screening with computer vision could possibly speed up the whole process of checking for hazardous objects.

Moreover, computers are able to see things that human eyes sometimes cannot see. This has important consequences for medical applications, as an algorithm may be able to detect illnesses in medical images earlier in time than a doctor. This could lead to better treatment, and more lives saved. More generally, if we want to build an intelligent machine capable of reasoning about its surrounding environment, we want it to understand what it sees.

There are plenty of possible applications to visual recognition technology. But understanding the content of images is extremely challenging, as it requires such systems to deal with variations present in visual data, that we discuss next.

Challenges

When observing pictures, humans are able to understand their content and ignore imaging conditions such as changes in the point of view or lighting, occlusions or truncations, as well as cluttered environments. Our perception of an image tends to be invariant to these changes. In data, these changes are additional modes of variation against which robustness needs to be implemented in a recognition algorithm. When trying to recognize objects, an algorithm needs to address several problems such as illustrated in the examples below.

Viewpoint and imaging conditions. Depending on how a picture was taken, objects can have different appearance in an image. We show an example in Figure 1-1. A visual recognizer should be able to recognize a chair from different points of view, e.g. a close-up view, or from the top, or from afar.

Lighting conditions. If the light is a little dimmer in a picture, an algorithm should still be able to recognize the objects that are present. Recognition should be invariant to lighting conditions, ideally.

Figure 1-1: Variability in imaging conditions. These chairs can have unusual appearance, in particular the middle example seen from above. Images from the Pascal VOC dataset [START_REF] Everingham | The pascal visual object classes (VOC) challenge[END_REF]). Figure 1-4: Intra-class variability. These examples of motorbikes seen from similar points-of-view, can present large differences in appearance while corresponding to the same class or category of objects. Images from the Pascal VOC dataset [START_REF] Everingham | The pascal visual object classes (VOC) challenge[END_REF]).

Occlusions. Some parts of objects may be hidden behind another object, as we show in Figure 1-2. These make objects more difficult to recognize, as only some parts of them are visible. When the configuration of an object is such that it partly occludes itself, we talk about self-occlusion.

Background clutter. In images, objects are not necessarily on a clean background, and other elements in the background may possibly distract a visual recognizer.

Deformations. This mode of variation happens more in the case of animals, that can be seen in a variety of poses. We show the example of cats in Figure 1-3, but this is especially true for humans as well.

Intra-class variability. In the data, objects belonging to a same category can still present large differences in appearance. While the nature of the objects can be the same, some parts may look different, as we show on motorbikes in Figure 1-4. This is known as intra-class variability and is a consequence of human decisions: it depends on how the data is labeled by annotators. Some of the invariances mentioned above can be quite complex, and in order to build robustness against them, methods rely on empirical approaches, using machine learning as we will discuss next.

Visual recognition as a machine learning task

The different modes of variation in images can be difficult to express formally. Therefore, machine learning methods are used to learn these modes of variation from labelled data. In visual recognition, image classification is a base building block.

Image classification. Let us take a look at a simple dog vs. cat classification task.

Given an image, the task consists of determining whether an image contains a cat or a dog.

We can solve the task in Figure 1-5 because we can rely on appearance; Convolutional neural networks. Among these machine learning approaches for computer vision, convolutional neural networks have recently attracted attention because of their great performance for visual recognition, outperforming all alternatives as we will describe in Chapter 2. These algorithms, invented in the '80s, will be the main focus of this thesis.

The issue of interactions with objects. Let's assume an image classification algorithm let us find images that contain a person and a phone. At that point it is quite possible that the person is using a phone, as we show in Figure 1-7. However, one may be interested in answering a more precise question, such as: is this person phoning, texting or taking a picture?

Figure 1-7: Recognizing interactions with objects is one step beyond object recognition, and we are now interested in how a person interacts with an object.

Solving this task should be possible as well, but may require interpreting more subtle cues, such as the positioning of the hands on the phone, the relative position of the phone to the head. Knowledge of the presence or absence of a phone is not sufficient anymore to provide an answer, and therefore we need more data to capture the corresponding patterns. However, since it is possible for a person to interact in different ways with a given object, the number of possible actions grows quicker than the number of different objects: this means that solving this task may require more data. In general, algorithms deliver higher performance on tasks when trained with more data. And for more difficult tasks, more data is necessary to obtain good performance. But data is in general not readily available as we discuss next.

The cost of data collection. In order to be exploited by current algorithms, images need to be annotated to provide supervision to the machine. In the supervised learning context, an input is provided to an algorithm as well as the desired output.

This means that the limit on the complexity of tasks that we can solve is set by how difficult it is to annotate data, keeping in mind that it gets harder to reach human agreement (labeling consistency across examples) for more abstract tasks.

One possible issue is the granularity of labeling; for example, should an example be labeled as cooking, chopping onions, or both ?

While the presence of more data should be beneficial to cover the different modes of variability of images, obtaining data has a cost. In the current supervised learning paradigm, the only recognition tasks that can be addressed are the ones for which there is enough human agreement to crowdsource data collection efficiently. In crowdsourcing applications such as Amazon Mechanical Turk, an annotation task is proposed to a worker in exchange for a small amount of money. If the task is difficult then annotating an example costs more. To decrease that cost, one can consider tasks for which smaller amounts of data are necessary, or for which data collection is easier.

The cost of data is one of our main concerns; some tasks, such as recognizing the presence of objects, can be solved with high enough performance to be deployed at a large scale in industrial applications. But more difficult tasks such as recognizing interactions between humans with objects, may require too much data to be solved reliably. Therefore in this thesis we are interested in methods requiring less annotations in the data. The hope is that if algorithms were able to learn from less annotations (or no annotations at all), they should have access to more data examples, and be potentially able to solve more difficult tasks.

Goals of this thesis

Even though annotating data is an expensive and limited process it is still reasonable in the case of objects, where human agreement is easy to obtain, allowing to build large databases such as ImageNet [START_REF] Russakovsky | ImageNet large scale visual recognition challenge[END_REF]) which appeared in 2009.

ImageNet provides a massive source of annotated data to the research community, exceeding in size everything that was available before, and paving the way for new algorithms. Building on this database, [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] demonstrated in 2012 how to use a dataset of a million images to train the largest neural network ever built at that time, winning the 2012 ImageNet Large-Scale Visual Recognition Challenge (ILSVRC-2012) by a large margin as we will describe in Chapter 2. Outperforming all other methods, this work revealed the full potential of convolutional neural networks for visual recognition, which will be the main focus of this thesis. But annotating and using one million images may be too costly to collect for any given task, and neural networks need a lot of data to perform well.

Transferring learned image representations. The first goal of this work is to find how to obtain the performance of large neural networks on other visual recognition tasks, without paying the cost of annotating large datasets, nor spending time building a working training setup from scratch.

Learning from weak supervision. The second goal of this work is to understand how precise annotations should be in order to solve a task with a convolutional neural network. The main question is whether data should be provided with the exact answers that are expected from the algorithm afterwards, or if it is possible to design a smarter algorithm, that can learn from less precise hints. Can we learn to localize objects only using less expensive image-level annotations?

Learning without manual supervision. Pushing this idea to the limit, we are interested in which regularities are natively present in data, if these can be retrieved only by observing data without any form of supervision, and if they can be useful for training algorithms. This unsupervised learning is the holy Grail of machine learning; our third goal is to explore this direction with convolutional neural networks.

1.5 Outline and contributions of this thesis

Outline

This manuscript contains six chapters including this introduction and a conclusion chapter, and two technical background appendices.

Related work.

In Chapter 2, we will present an overview of previously published work related to our goals. The work of [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] on ImageNet, published shortly before the beginning of this thesis, sparked great interest in neural networks from the computer vision community. Therefore, we will review the fields of visual recognition and neural networks, and illustrate the paradigm shift following the ImageNet event. We will point out that already in the 90's neural networks were very close to their current form, awaiting the technology and data made available only in the recent years to demonstrate their performance. Today, most state-of-the-art visual recognition systems involve a neural network component.

Learning and transferring mid-level image representations. In Chapter 3

we will present our first contribution, the study of a procedure called "pre-training" that leads to important improvements for many tasks in computer vision. The idea is the following: we first train a large neural network on a task for which we have plenty of data. Then, we show that the image representations learned by this network can be efficiently transferred to other visual recognition tasks where less data is available, leading to significant improvements. In particular, we show that the image representations lead to higher performance when the network is pre-trained with more data.

This technique allows leveraging the power of very large and powerful neural networks to smaller-scale tasks involving natural images. Pre-training is now a standard procedure in computer vision, eliminating the long process of training large networks from scratch.

Weakly supervised learning. In Chapter 4 we will present our second contribution, the study of the behavior of neural networks in the context of weak supervision.

We observed that classification neural networks respond strongly to the most distinctive parts of objects, such as the heads of cats and dogs, or the wheels of a car. We extended this behavior to images and trained a neural network only with information on the presence or absence of objects in images; we observed that the algorithm was capable of retrieving the location of these objects, an information not available at training time, by relying on statistical regularities present in the data. This setup is an example showing it is possible for an algorithm to learn with less precise supervision than what was previously expected.

Unsupervised learning. In Chapter 5 the focus will be on unsupervised learning; first we will describe Generative Adversarial Networks (GANs, [START_REF] Goodfellow | Generative adversarial nets[END_REF]), a recent class of generative models implemented as neural networks, that aim at learning the distribution of a set of images to generate new samples. This method, delivering appealing results, greatly increased the interest of the community on unsupervised learning, and the corresponding field is now very active. In this chapter, much more exploratory, our goal is to understand the underlying issues better and also expose trails worthy of study on this problem. We investigate the GAN evaluation problem and possible links with the concept of causality, for which we propose the use of classifier-based statistical two-sample tests. We also investigate the difficult subject of distances between distributions of images, related to GANs, and expose insights on what these algorithms are learning building on recent work on optimal transport.

Technical background. In addition to the main text, in Appendices A and B we provide technical background covering the mathematical and machine learning notions necessary for understanding the rest of the thesis. These appendices correspond to an effort to explain that neural networks are conceptually simple methods, despite the difficulties that are met in practice. We describe convolutional feed-forward neural networks and their associated learning algorithms. In particular, we present their core elements and explain how they leverage the power of GPUs through linear algebrabased operations. We show that neural networks correspond to a restricted class of parameterized functions, following an architecture, that fit into a simple gradientbased machine learning framework.

Publications

The material in Chapter 3 was published and selected for an oral presentation in CVPR 2014 under the title: Learning and Transferring Mid-Level Image Representations using Convolutional Neural Networks, [START_REF] Oquab | Learning and transferring mid-level image representations using convolutional neural networks[END_REF].

The material in Chapter 4 was published in CVPR 2015 under the title: Is object localization for free? -Weakly-supervised learning with convolutional neural networks, [START_REF] Oquab | Is object localization for free?-weakly-supervised learning with convolutional neural networks[END_REF].

In addition, an extension of Chapter 4 was published in ECCV 2016 under the title: "ContextLocNet: Context-Aware Deep Network Models for Weakly Supervised

Localization", [START_REF] Kantorov | Contextlocnet: Context-aware deep network models for weakly supervised localization[END_REF].

Parts of Chapter 5 (Sections 5.3 and 5.4.2) were published in ICLR 2017 under the title: "Revisiting Classifier Two-Sample Tests", Lopez-Paz and Oquab [2017].

Software contributions

Apart from software to reproduce results of the published papers, during the course of this thesis, we also shared open-source GPU code packages for the Torch7 software (Collobert et al. [2011a]). These contributions include a GPU convolution code (https://github.com/qassemoquab/nnbhwd) and jittering code using texture units (https://github.com/qassemoquab/texfuncs) for real-time data augmentation, that we used for our work in Chapter 4.

We also contributed an implementation of Spatial Transformer Networks [START_REF] Jaderberg | Spatial transformer networks[END_REF]) including a flexible and efficient bilinear interpolation code for images (https://github.com/qassemoquab/stnbhwd, starred 242 times). Our package was notably used in the gvnn package (Geometric Vision, [START_REF] Handa | gvnn: Neural network library for geometric computer vision[END_REF]), and various papers (e.g. Johnson et al. [2016], [START_REF] Reed | Learning what and where to draw[END_REF]).

Chapter 2

Related work

In this chapter, we present early work on neural networks and computer vision separately, underlining important contributions that shaped the corresponding research along the years. Then, we describe the collision between these fields, that happened in 2012 with the success of [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] in the ImageNet visual recognition challenge. Finally, we overview subsequences of this event that caused changes in the majority of areas of visual recognition.

In Section 2.1, we focus on the history of computer vision methods, underlining the importance of feature descriptors such as SIFT in vision pipelines. In Section 2.2, we focus on neural network methods, in particular showing that the algorithms used today are similar to the ones that have been developed in the '80s. In Section 2.3, we describe the ImageNet competition event, and the following unexpected increase of interest in neural networks from the computer vision community, notably through feature descriptors built from neural networks. Our work in Chapter 3 fits within that period and we provide more related references in this section. In Section 2.4

we then overview the current trend of integrating components of computer vision pipelines within neural network architectures with improved features and end-to-end differentiable setups. In Section 2.5 we discuss the problem of limited annotation and describe approaches leveraging weaker forms of supervision; we then review methods for weakly-supervised object localization, related to our work in Chapter 4. We also discuss recent approaches on unsupervised learning with neural networks and in particular Generative Adversarial Networks, related to our work in Chapter 5.

Early days in vision

Figure 2-1: One of the earliest approaches in Computer Vision, by Roberts [1963].

Roberts attempts to reconstruct a three-dimensional shape from a picture.

Geometrical models. One of the first approaches to computer vision dates back to 1963 with the PhD thesis of L.G. Roberts [START_REF] Gilman | Machine perception of three-dimensional solids[END_REF]), attempting to reconstruct a three-dimensional shape from a two-dimensional picture, using the information of the edges, and assuming planar surfaces, as shown in Figure 2-1. Reconstruction of simple geometric shapes was pushed further in the following decades. [START_REF] Richard | Use of the hough transformation to detect lines and curves in pictures[END_REF] introduce the Hough transform to detect lines. [START_REF] Canny | A computational approach to edge detection[END_REF] proposes an edge detector to simplify the content of images. Huttenlocher [1987] presents a recognition approach by aligning an image of an object with a corresponding 3D CAD model.

As explicit 3D object reconstruction from images has shown to be difficult, another line of work focuses on studying so-called invariants, i.e. view-invariant object signatures in the image. [START_REF] Weiss | Projective invariants of shapes[END_REF] looks for invariants by studying the projective nature of image formation. [START_REF] Rothwell | Canonical frames for planar object recognition[END_REF] build on projective invariants to propose a method for recognizing planar objects from images. Planar objects are particularly interesting because the appearance variability, e.g. due to illumination, is much lower. [START_REF] Burns | View variation of point-set and line-segment features[END_REF], however, establish that there are no general-case view-invariants for real three-dimensional objects.

Figure 2-2: Eigenfaces [START_REF] Turk | Eigenfaces for recognition[END_REF]). The dataset (left) is used to compute the principal components (right): new faces are projected on the PCA subspace, and the resulting coordinates are used for recognition.

Appearance models. As the growing power of computers allows for more realistic images, the community becomes interested in more complicated three-dimensional objects, for which the variability in appearance becomes too complicated for mathematical study. Appearance-based methods start to emerge in the '80s, building object models from many image samples (image datasets). Early work in this direction has focused on face recognition. [START_REF] Sirovich | Low-dimensional procedure for the characterization of human faces[END_REF] propose to decompose face images onto a low-dimensional space, applying Principal Component Analysis on a dataset of faces. [START_REF] Turk | Eigenfaces for recognition[END_REF] improve on this approach by introducing Eigenfaces in 1991, a near-real-time system that can recognize faces using an Euclidean distance in the PCA space, see Figure 2-2. [START_REF] Murase | Visual learning and recognition of 3-d objects from appearance[END_REF] extend this approach to represent objects. They build a dataset of objects in different poses (rotated by different angles) on a uniform background. Using a PCA, as in Eigenfaces, allows them to recognize objects and poses simultaneously, effectively implementing pose invariance for objects as shown in Figure 23.

Histograms and vocabularies. The work on appearance models sets a trend for object recognition and in this context , [START_REF] Michael | Color indexing[END_REF] propose associating objects to a histogram of their colors, and introduce a comparison operator called histogram intersection. This allows recognizing instances of objects robustly, as the distribution of colors remains unaffected by small viewpoint changes. But recognizing colors is difficult because of illumination changes, and [START_REF] Schiele | Object recognition using multidimensional receptive field histograms[END_REF] extend this histogram approach by considering the responses of an image to convolution filters (such as Gabor filters or Gaussian derivatives). This allows recognition based on the distribution of local features such as edges. [START_REF] Leung | Representing and recognizing the visual appearance of materials using three-dimensional textons[END_REF] adopt a similar approach for recognizing textures, by considering histograms of local features called 3D textons. These textons are built by concatenating the responses of [2004]). This method combines the bag-of-visual-words approach with SVM classifiers to perform visual recognition.

From instance-level to category-level recognition. The location-agnostic bagging approach shows that recognition may succeed even if spatial information is lost. [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF] adopt a similar approch with the bags of keypoints: constructing a vocabulary of patch descriptors extracted at interest points using the Harris Affine method [START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF]) on a dataset of labeled images, describing images as a histogram of these words then classifying them into their corresponding classes using the SVM (Support Vector Machine, [START_REF] Schölkopf | Learning with kernels: support vector machines, regularization, optimization, and beyond[END_REF])

algorithm. This method made visual categorization popular and robust by treating statistically concepts defined within a dataset only by examples, with large variations in viewpoints . This corresponds to a crucial step in computer vision, shifting the focus from instance-level recognition (recognizing a specific object) to category-level recognition (recognizing the nature of an object). consists of describing objects as a constellation of parts with constraints between them, as shown in Figure 2-11. By reasoning at the level of object parts, these methods have potential for much more precise localization of the objects that are recognized, and this idea proved fruitful. [START_REF] Marr | Representation and recognition of the spatial organization of three-dimensional shapes[END_REF] propose to represent complex shapes as a hierarchy of geometric primitives such as cylinders, as

shown in Figure 2-12. [START_REF] Ioffe | Probabilistic methods for finding people[END_REF] build on a similar idea but adopting a bottom-up approach, by first detecting candidate segments corresponding to human limbs, and then considering the underlying kinematic constraints to assemble them using a human body model to perform person detection in images, as shown in Figure 2-13. Fergus et al. [2003b] propose an object model based on a constellation of parts, with built-in tolerance to deformations. This approach recognizes parts of objects then connects them together before evaluating them against a learned graph model of the classes of interest, as shown in Figure 2-14; this approach enables category-level recognition and localization of objects. Object detectors. With the progress of visual recognition, object detection (recognizing an object category and predicting its extent with a bounding box, as shown in Figure 2-9) gains popularity, and one influential algorithm is the person detector of [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]; this method first collects gradient information within cells of a grid applied on an image at multiple scales using Histograms of Gradients, then matches these extracted features against a learned person model, represented by the SVM weights as shown in Figure 2-15.

Then, combining these Histograms of Gradients features with the constellation models described above and the spatial pyramid approach of [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF], [START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF] introduce the deformable part-models (DPM, see Figure 2-16) using a new training method for SVM algorithms (the Latent SVM ). This model is improved and evaluated in a follow-up paper [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF], Figure These methods propose a small set of candidate bounding boxes for object detection; in contrast, a dense sliding-window approach would propose a much larger set of boxes. As a result, using more refined feature transforms becomes affordable on large-scale datasets, as there are fewer candidates to process. This approach is used in the more recent R-CNN object detector to be described in Section 2.3.

Conclusion.

This section presents the history and some of the key paradigms in visual recognition. Starting with three-dimensional simple shapes, the community progressively introduced image datasets to learn models of visual appearance. Meth- [START_REF] Rosenblatt | The perceptron: A perceiving and recognizing automaton[END_REF]), one of the earliest machine vision systems in history.

Early days in neural networks

Hebb's rule. The history of Artificial Neural Networks goes back to 1949. Hebb, neuropsychologist, studies the human biological brain and connects it to the idea of the mind in his book The Organization of Behavior [START_REF] Hebb | The organization of behavior: A neuropsychological theory[END_REF]). He popularizes the Hebb's rule : neurons that fire together, wire together, paving the way towards complex arrangements of neurons, which are the neural networks of today.

Perceptron. [START_REF] Rosenblatt | The perceptron: A perceiving and recognizing automaton[END_REF] builds what is known as one of the first computer The Neocognitron architecture [START_REF] Fukushima | Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position[END_REF]) introduces shiftinvariance into neural networks together with pooling layers (as "complex units" 𝑈 𝐶 ). This multi-layered architecture is very close to the modern neural network architectures that we use today.

Neocognitron. Inspired by the neural connectivity pattern discovered by [START_REF] Hubel | Receptive fields of single neurones in the cat's striate cortex[END_REF] in the cat's visual system, Fukushima's Neocognitron [START_REF] Fukushima | Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position[END_REF], see Figure 2-21) replaces the association layer by alternating layers of simple and complex threshold units. The simple layers are trained using an unsupervised procedure related to clustering, the complex layers are fixed pooling transforms, and the whole architecture is motivated by its ability to compute features that are robust to changes in the position of the object in the receptive field. As a result, groups of S-cells in simple layers, arranged in two-dimensional arrays (cell-planes) respond to the same stimulus, while the C-cells aggregate the responses from neighboring S-cells in a plane.

The Neocognitron effectively implements shift invariance, which is known to be, today, an important property of vision systems: be it on the top-left or bottom-right of an image, a given object is still the same object. Similarly, the pooling transforms in the complex layers implement robustness to small deformations and are widely used in modern neural networks. [1989] with the convolution layer, corresponds to the first successful application of convolutional neural networks.

Backprop. Neocognitron was lacking a supervised learning algorithm, and therefore could not be used for a specific purpose. However, a couple years after, [START_REF] Rumelhart | Learning representations by back-propagating errors[END_REF] introduce the backpropagation algorithm, which is a generalization of the chain rule for differentiating functions, making gradient computation possible in multi-layered systems. Using backprop, [START_REF] Lang | A time delay neural network architecture for speech recognition[END_REF] propose speech recognition using a translation-invariant neural network that convolves a set of weight patterns with the contents of a sliding window on one-dimensional acoustic signal.

Convnets. [START_REF] Lecun | Backpropagation applied to handwritten zip code recognition[END_REF] extend the work of [START_REF] Lang | A time delay neural network architecture for speech recognition[END_REF] to the two-dimensional domain with the multi-convolution layer (see Figure 2-23), building on the weight sharing scheme of the S-cell planes of Fukushima's Neocognitron. This method quickly achieves excellent results in handwritten digit recognition (see Figure 2 -22). Though processing two-dimensional signals (as images) with backprop and weight sharing is mentioned in [START_REF] Rumelhart | Learning representations by back-propagating errors[END_REF], the digit recognition problem is the first successful and convincing incarnation of this idea. The setup is run on SN (Simulateur de Neurones, [START_REF] Bottou | Sn: A simulator for connectionist models[END_REF]), one of the earliest pieces [START_REF] Lang | A time delay neural network architecture for speech recognition[END_REF] propose an alternative where the weights of the networks are updated after presenting each pattern, "departing to some extent from a true gradient Figure 2-24: [START_REF] Bottou | Stochastic gradient learning in neural networks[END_REF] (updated in [START_REF] Bottou | Online algorithms and stochastic approximations[END_REF]) provides a convergence proof of SGD towards extremal points (shown here), notably showing the issue of poor solutions like saddle points and asymptotic plateaus.

descent". This procedure, although not named as such in the paper, corresponds to stochastic gradient descent (SGD). The corresponding theory is formalized in 1991,

and [START_REF] Bottou | Stochastic gradient learning in neural networks[END_REF] (updated in [START_REF] Bottou | Online algorithms and stochastic approximations[END_REF]) provides a proof for the convergence of SGD towards extremal points (see Figure 2 Graph Transformer networks and general architectures. In 1997, neural networks have successful industrial applications in handwritten character recognition, and they are used for automatically reading checks in the USA with a system described in [START_REF] Lecun | Reading checks with graph transformer networks[END_REF]. The Graph Transformer Networks (GTN) approach consists of building a whole system with arbitrarily complicated parameterized modules, as long as they are differentiable. We illustrate in Figure 2-25 the GTN architecture proposed for recognizing digit strings in checks, combining: a segmenter, a trainable neural network that recognizes digits, and graph-processing differentiable modules that allow propagating gradient to the neural network weights. With this type of approach, a complex heterogeneous system can be trained end-to-end with gradient descent methods.

In the GTN approach the input is first over-segmented, leading to a segmentation graph 𝐺 𝑠𝑒𝑔 where the graph edges correspond to possible character classes. These then it does not receive learning signal as the contributions sum to zero.

At test time, we obtain the output of the system from the right branch. This GTN architecture shows that it is possible to train a neural network component inside a complex system of differentiable modules. We also note that the supervision for this setup is provided in an intermediate step, through the path selector module, and not directly by the loss function.

Vanishing gradient and LSTM. Recurrent neural networks, mentioned in Lang [START_REF] Lang | A time delay neural network architecture for speech recognition[END_REF], are a special form of neural networks where recurrent units are connected to themselves, making them especially useful for learning models for sequential data. The presence of a hidden state reminds of Hidden Markov Models. [START_REF] Bengio | Learning long-term dependencies with gradient descent is difficult[END_REF] notice that, in longer sequences, neural networks have difficulties storing ("latching") information because of the vanishing gradient problem. This phenomenon, although common when processing data through many stages in an architecture, is even more important in the recurrent case where data can be processed [START_REF] Hochreiter | Long short-term memory[END_REF]. The LSTM uses a gating approach to update or output the relevant contents of the hidden state (the Constant Error Carrousel ) in the center.

an arbitrary number of times through small-slope non-linear functions such as the hyperbolic tangent, leading to small-magnitude gradients.

In order to solve this issue, [START_REF] Hochreiter | Long short-term memory[END_REF] propose Long-Short Term Memory (LSTM), a recurrent neural network architecture that learns when it should store and forget the data that it stores in its hidden state, as shown in Figure 2-26.

Maturity. The procedures are studied well, common pitfalls are listed, and tricks are proposed in LeCun et al. [1998b], which is very close to a user manual for training neural networks, containing many pieces of advice still useful today. One can notably observe the similarity between the modern AlexNet architecture and the LeNet-5 architecture in Figure 2-32. In the end of the '90s, neural network methods are essentially mature: they can be used as soon as there is enough data and processing power. However, at that time the data-hungry nature of neural networks limited their usage in computer vision, and the community obtained generally better performance on visual recognition with pipelines relying on the hand-made SIFT descriptor features and convex SVM classifiers allowing for easily reproducible results. Feature learning. Feature extraction seemed to be the limiting factor to the success of neural networks in vision tasks for which the datasets were small, and trails have been explored to alleviate this problem based on unsupervised feature learning, hoping to compete with the SIFT descriptor. Restricted Boltzmann Machines [START_REF] Hinton | Reducing the dimensionality of data with neural networks[END_REF]) revived interest in deep architectures by providing a pretraining initialization method for weights in deep neural networks, leading to initial weights being neither too large (they lead to poor local minima during optimization) nor too small (gradients cannot be propagated efficiently with backprop), [2007b]. [START_REF] Kavukcuoglu | Learning invariant features through topographic filter maps[END_REF] propose to pool groups of learned convolution filters according to topographic maps to build invariance explicitly (shown in Figure 2 -29). But these methods struggle with stacking many of these layers and, while the results are promising, depth remains an issue. Later, Collobert et al. [2011b] show that an unsupervised approach for learning features (or embeddings) can be successful with neural networks in the case of Natural Language Processing; similarly, [START_REF] Le | Building high-level features using large scale unsupervised learning[END_REF] manage to train a network with an unsupervised approach on large amounts of images using a distributed system of 10000 CPUs (see Figure 2 -30), giving more hopes in this direction.

ReLU. One very important contribution during the neural network winter is the study of issues related to depth and vanishing gradient (mentioned in 1994 in [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] study the issue and propose an initialization scheme that allows for better gradient flow through saturating non-linearities (close to the one proposed in LeCun et al. [1998b]). Pushing the reasoning further, Glorot Conclusion of this section. In this section, we show that neural networks were extremely advanced and successful already in the '90s. Little has changed in their design when compared to the systems used today. Even though the work of [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] has revived them and more improvements have happened since, we want to point out that the algorithms are mostly identical; the much larger scale of data and hardware has changed the game. [1998a], is very close to the more recent AlexNet (bottom, 8-layers deep) architecture, proposed in [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF].

The AlexNet breakthrough

Consequences

Improved image descriptors. While representations based on hand-crafted descriptors such as SIFT and HoG have been shown to work well in practice for vision, it is unclear whether they should be optimal for the task. This question raised con- In particular, we observed that given the data-hungry nature of neural networks, their performance scales up with the amount of data provided for training. This is important because once a neural-network-based system is operational, an easy way to increase its performance is simply to collect and train with more data.

Interestingly, building a feature transform on a task A (the source task) then using the learned knowledge on a task B (the target task) can also be seen as a form of transfer learning, as described in [START_REF] Pan | A survey on transfer learning[END_REF], to alleviate small amounts of training data. While [START_REF] Ahmed | Training hierarchical feed-forward visual recognition models using transfer learning from pseudo-tasks[END_REF] propose this transfer in a CNN using unsupervised pseudo-tasks, other works in computer vision [START_REF] Aytar | Tabula rasa: Model transfer for object category detection[END_REF], [START_REF] Tommasi | Safety in numbers: Learning categories from few examples with multi model knowledge transfer[END_REF], [START_REF] Farhadi | A latent model of discriminative aspect[END_REF], [START_REF] Khosla | Undoing the damage of dataset bias[END_REF], Saenko et al.

[2010]) focus on classifiers rather than on descriptors.

Building on the AlexNet result, [START_REF] Sharif Razavian | Cnn features off-the-shelf: an astounding baseline for recognition[END_REF] advocate the usage of CNN features in an "off-the-shelf" manner, by using models readily available online to improve the performance of vision algorithms; open-source feature extractors based on CNNs (e.g. OverFeat [START_REF] Sermanet | Overfeat: Integrated recognition, localization and detection using convolutional networks[END_REF], Caffe [START_REF] Jia | Caffe: Convolutional architecture for fast feature embedding[END_REF]) also appear along with trained models, standardizing this procedure and shifting the focus to better CNNs and CNN features. The "AI" explosion. With the success of neural networks on ILSVRC-2012, large investments were made by companies; we mention only three of them here. Google hired the creators of AlexNet [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF]) early 2013 by acquiring their company5 . Google uses neural networks in, among other applications, to its voice transcription engine6 and its translation service [START_REF] Wu | Google's neural machine translation system: Bridging the gap between human and machine translation[END_REF] [START_REF] Silver | Mastering the game of go with deep neural networks and tree search[END_REF]), beating world-class Go players for the first time, similar to the DeepBlue success [START_REF] Campbell | Deep blue[END_REF]) on the game of chess.

Deeper architectures. Given the crucial role of parallel computations in CNN architectures, the GPU industry (in particular nVidia, thanks to its ownership of the CUDA language for GPU programming) underwent quick progress on hardware, allowing more improvements on neural networks. [START_REF] Chetlur | cudnn: Efficient primitives for deep learning[END_REF] notably introduce the cuDNN library as a standard set of subroutines for neural network computations similar to the Basic Linear Algebra Subprograms formalism (BLAS, Lawson et al. [1979]).

More powerful GPUs and computation libraries set a trend for exploring deeper CNN architectures further decreasing error rates in the ILSVRC challenge:

• OverFeat (9 layers, [START_REF] Sermanet | Overfeat: Integrated recognition, localization and detection using convolutional networks[END_REF], 13% top-5 error)

• VGGNet (19 layers, Simonyan and Zisserman [2014b], 7% top-5 error)

• GoogLeNet (22 layers, [START_REF] Szegedy | Going deeper with convolutions[END_REF], 7% top-5 error)

• ResNet (152 layers, [START_REF] He | Deep residual learning for image recognition[END_REF], 4% top-5 error)

In particular, better performance on ImageNet classification leads to better CNN features, improving the performance on other visual recognition tasks.

Democratization. Neural networks are powerful, but they are known to be difficult to train properly, as mentioned in LeCun et al. [1998b] when discussing the backpropagation algorithm: "getting it to work well, and sometimes to work at all, can seem more of an art than a science". As a consequence, along with the streak of successes starting with AlexNet, efforts were made to build tools to ease the task of training neural networks.

Among these tools, the important batch-normalization layer [START_REF] Ioffe | Batch normalization: Accelerating deep network training by reducing internal covariate shift[END_REF]) was introduced: during mini-batch training, the output values of weighted layers are normalized with respect to the mean and standard deviation across examples in a differentiable manner; the authors report better, faster and easier training.

The success and ease-of-use of this method led to its implementation in an optimized version in the cuDNN computation library.

New adaptive learning rate algorithms, variants of SGD, were also introduced to deal with the issue of setting learning rates properly in the networks, providing theoretical justifications in some cases (neural networks are mathematically difficult). [START_REF] Schaul | No more pesky learning rates[END_REF] propose using second-order (Hessian) information. [START_REF] Tieleman | Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude[END_REF] propose RMSprop, dividing the gradient by a running average of its recent magnitude, justified by empirical evidence. In our work described in Chapter 4, we used the Adagrad algorithm proposed in [START_REF] Duchi | Adaptive subgradient methods for online learning and stochastic optimization[END_REF] that adjusts learning rates for each parameter, more effective when the gradients are sparse. Kingma and Ba [2015b] propose Adam, adjusting learning rates depending on the first-order and second-order moments of the sequence of gradients for each weight parameter in the network; we use Adam in our work in Chapter 5. With these new tools, neural networks have become easier to train, increasing their popularity further.

Conclusion of this section. In this section, we show that the goal of learning competitive image features, pursued by the neural network community using unsupervised methods, was finally met when the amount of data and the computational power reached a critical point in 2012 with AlexNet. Unexpectedly, these powerful CNN features were obtained with purely supervised methods, very similar to the state of the art in the '90s. Early evidence shows that they compare favorably to previous methods such as those based on SIFT, and their widespread success led to massive investments in the field, a larger community, better hardware and easier methods allowing progress towards more powerful models, effectively democratizing neural networks.

Integrating vision pipelines in neural networks

In this section we show the trend of integrating more complex vision systems within unified neural networks. Building heterogeneous systems is similar in spirit to the Graph Transformer Networks approach of [START_REF] Lecun | Reading checks with graph transformer networks[END_REF] shown in Figure 2-25, Section 2.2. In contrast to the use of CNN features discussed in Section 2.3, it is possible to train end-to-end computer vision systems by expressing all processing steps as differentiable modules.

Object detection. Object detection is the computer vision task that consists of finding individual instances of objects in images, recognizing their classes and predicting their extents in terms of bounding boxes. Extracting the content of an image in this way should be useful for reasoning and understanding based on visual input.

This task was popularized with the Pascal VOC challenge, and earlier methods solving this task, such as the Deformable Part Models algorithm, are described in Section 2.1.

With the appearance of more powerful feature transforms, object detection underwent a significant increase in performance with the R-CNN approach [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF], described in Figure 2-37), building on the Selective Search algorithm from van de Sande et al. [2011] (see Figure 2-19, Section 2.1). This method is further improved in a Fast version [START_REF] Girshick | Fast R-CNN[END_REF]), and a Faster version [START_REF] Shaoqing Ren | Faster R-CNN: Towards real-time object detection with region proposal networks[END_REF]) that proposes to integrate the object proposal step as a differentiable module within a more complex neural network.

In parallel to R-CNN, the OverFeat detector [START_REF] Sermanet | Overfeat: Integrated recognition, localization and detection using convolutional networks[END_REF]) provides a different approach for object detection, by running a sliding window classifier densely on an image, using the convolutional properties of neural networks to share computation as explained in Figure 2-38, before feeding the result to a regressor network that provides bounding box coordinates as output. With neural networks, two important methods appear. One of them, proposed by [START_REF] Tran | Learning spatiotemporal features with 3d convolutional networks[END_REF], adopts an approach similar to AlexNet, by learning a Convolutional Neural Network using spatio-temporal convolution (see Figure 2-49) on a large dataset of videos (Sports-1M, proposed by [START_REF] Karpathy | Large-scale video classification with convolutional neural networks[END_REF]) in a supervised manner, then using the CNN features learned in this way to perform classification on other datasets.

(a) 2D convolution on multiple frames (b) 3D convolution The other one, proposed by Simonyan and Zisserman [2014a] and shown in Figure 2-50, is close to the IDT approach in the sense that it merges appearance information with optical flow information in what is called a Two-Stream architecture. We can observe that this integrates the processing of these two modalities within a single network architecture. Following a similar trail, [START_REF] Arandjelović | Look, listen and learn[END_REF] also propose using sound as an additional modality for recognition in videos.

Recent work by [START_REF] Carreira | Quo vadis, action recognition? a new model and the kinetics dataset[END_REF] combines the two approaches by running the spatio-temporal convolution of [START_REF] Tran | Learning spatiotemporal features with 3d convolutional networks[END_REF] on the image and flow modalities used in the Two-Stream architecture of Simonyan and Zisserman [2014a],

and obtaining state-of-the-art results by pretraining the network on the Kinetics dataset [START_REF] Kay | The kinetics human action video dataset[END_REF]).

Less supervision

The methods described in the previous section all rely on supervised datasets. In this section we are interested in ways to decrease the supervision necessary for a visual recognition setup to learn. Fully supervised methods require careful annotation of object location in the form of bounding boxes [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]), segmentation [START_REF] Yadollahpour | Discriminative re-ranking of diverse segmentations[END_REF]) or even location of object parts [START_REF] Brox | Object segmentation by alignment of poselet activations to image contours[END_REF]), which is costly and can introduce biases. For example, should we annotate the dog's head or the entire dog? What if a part of the dog's body is occluded by another object?

Weak supervision

Many ways to provide supervision. Alternatively, it is possible to obtain weak image-level annotations, and they are less expensive to produce: for instance it is easier to annotate an image with the presence of an object than to draw a bounding [START_REF] Joulin | Learning visual features from large weakly supervised data[END_REF] propose learning the first layers of a CNN using also text annotations. [START_REF] Doersch | What makes paris look like paris[END_REF] use geographical meta-data from pictures to recognize cities; [START_REF] Prest | Learning object class detectors from weakly annotated video[END_REF] use YouTube videos to collect frames containing objects of interest using tracking, and train object detectors; [START_REF] Hejrati | Analyzing 3d objects in cluttered images[END_REF] annotate landmarks on car images to build a 3D car model then predict the pose of the car at test time; [START_REF] Shrivastava | Building part-based object detectors via 3d geometry[END_REF] build on RGBD (depth images)

to improve the DPM model of [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]. In a more abstract line of work, [START_REF] Chen | Neil: Extracting visual knowledge from web data[END_REF] and [START_REF] Divvala | Learning everything about anything: Weblysupervised visual concept learning[END_REF] attempt to learn relations between concepts with algorithms crawling the internet and extracting knowledge (see Figure 2-52).

To summarize, there are many different ways to obtain supervision, and the less precise annotations can sometimes be unexpensive and readily available. Therefore, there is interest in developing methods that solve tasks using as little supervision as possible, and the goal of weakly-supervised learning on images is to tackle the problem of expensive data collection. CNN features, inspired by the R-CNN approach [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF]). Similarly, the works of [START_REF] Wang | Weakly supervised object localization with latent category learning[END_REF], [START_REF] Gokberk Cinbis | Weakly Supervised Object Localization with Multi-fold Multiple Instance Learning[END_REF] build on Selective Search and CNN features to address the task, as well as [START_REF] Bilen | Weakly supervised deep detection networks[END_REF] along with our extension in [START_REF] Kantorov | Contextlocnet: Context-aware deep network models for weakly supervised localization[END_REF] 12 . Approach in this thesis. Our method uses supervision in the form of image-level labels indicating the presence or absence of objects in images, then coarsely predicts the locations of these objects in unseen images. Our CNN architecture relies on a global max-pooling operation which can be seen as a variant of Multiple Instance

6144 $ 2048 $ K$ K$ Rescale$ [$0.7…1.4$]$ chair$ table$ plant$ person$ car$ …$ C1=C5$ FC6$ FC7$ FCa$ FCb$ ConvoluBonal$feature$$ extracBon$layers$ AdaptaBon$layers$
Learning [START_REF] Foulds | A review of multi-instance learning assumptions[END_REF], [START_REF] Kotzias | Deep multi-instance transfer learning[END_REF], [START_REF] Viola | Multiple instance boosting for object detection[END_REF]) if we refer to each image as a "bag" and treat each image window as a "sample". As a result, our method is able to predict the approximate location of objects in complex cluttered scenes as described in Chapter 4. With this procedure, one can efficiently retrieve the image region that leads to a classification decision. Using the location predictions that are obtained in this way, [START_REF] Sun | Pronet: Learning to propose object-specific boxes for cascaded neural networks[END_REF] further extend our method with a verification network improving the classification performance on these datasets.

Conclusions.

Various approaches show that it is possible to learn from different modalities, such as text, or even geographical meta-data. Such supervision is often readily available on the Internet, encouraging new methods using less fully-annotated training data. In this section, we discuss methods able to learn from weak forms of

Unsupervised learning with neural networks

In the following, we discuss approaches attempting unsupervised learning with neural networks. The autoencoder line of research notably fits in this category, and we refer to Section 2.2 for a description of related works. Below we focus on the more recent self-supervised learning and Generative Adversarial Network approaches.

Self-supervision. The work of [START_REF] Ngiam | Multimodal deep learning[END_REF] proposes a multimodal autoencoder approach that given a video, attempts to reconstruct the sound from the image, or vice-versa (see Figure 2 -56). This form of supervision is free, as it relies only on using correlated signal from different modalities. As a result, this approach allows pre-training layers of a neural network that can then be used in a transfer scenario (as in Chapter 3), effectively learning CNN features without annotations, with the system supervising itself.

Following this line of work, [START_REF] Agrawal | Learning to see by moving[END_REF] and Jayaraman and Grauman The algorithm receives two patches in one of these eight possible spatial arrangements, without any context, and must then classify which configuration was sampled.

[2015] propose using ego-motion as a form of correlated signal in videos: the motion of the camera is recorded along with the visual input, providing an additional modality for learning. Also with videos, [START_REF] Wang | Unsupervised learning of visual representations using videos[END_REF] propose tracking objects in an unsupervised way, and training a network to generate similar representations (in the L 2 feature space) for two regions containing the same object. Doersch et al.

[2015] propose a different task with context prediction, where the task is to retrieve the spatial configuration of two patches extracted from a source image (see Figure 2-57). [START_REF] Zhang | Colorful image colorization[END_REF] propose using grayscale images to predict the colored versions, allowing them to build a colorization algorithm as well as learning features in a neural network (see Figure 2 -58). These works build on the idea that it should be necessary for a network to understand the content of images to accomplish the self-supervised task. • G generates a random sample 𝑥 from a random vector 𝑧 and passes it to D.

• D is trained to classify whether 𝑥 comes from the dataset or not.

• D provides gradient to G, communicating how G should modify its output to decrease the performance of D for classification.

• G adapts progressively, eventually providing more realistic samples.

This idea is applied to the image domain in Denton et al. Despite various successful applications, the understanding of the properties of GANs remains limited. For example, it is difficult to measure whether the generated distribution matches the reference data distribution. We discuss this subject further in our work in Chapter 5.

Conclusion of this chapter

In this chapter, we describe the progress of research in visual recognition and neural networks and the recent paradigm shift caused by the success of [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] in the ImageNet classification challenge of 2012.

In Section 2.1, we review the literature of computer vision with a focus on visual recognition before 2012. Early attempts at solving the problem of computer vision consisted of pure geometric methods. Given the difficulty and the numerous modes of variation of image data, the field started relying on empirical models through datasets, prompting the use of machine learning techniques to tackle recognition. Then, looking for suitable ways to represent images in this context, global representations were replaced progressively by local image descriptors such as SIFT in the 2000s, paving the way for efficient statistical approaches to instance-level object matching, and later category-level object recognition with SVMs. In parallel, refined techniques based on structured models were proposed, improving the localization of objects in images and eventually leading to object detection methods suitable for large-scale applications.

In Section 2.2, we review the literature related to neural networks before 2012.

Inspired by studies of the human brain, early architectures were proposed for visual recognition, and the introduction of the backpropagation algorithm made neural networks trainable. Successful applications were proposed for character recognition using Convolutional Neural Networks (CNNs), and implemented in real-world situations such as check-reading in the '90s. The technology was essentially mature already and very close to its current state, but the lack of data and computational resources at that time held back applications on realistic images. During the 2000s, with the quick progress of other computer vision methods based on hand-crafted feature descriptors, neural networks could not compete with the state of the art in the field of visual recognition, despite many attempts at feature learning with unsupervised approaches: this was the "winter" of neural networks.

In Section 2.3 we review the ImageNet competition event that occurred in 2012.

The growing scale of Internet in the 2000s and the wide spread of image capturing devices such as smartphones have made visual data available in large amounts.

Driven by the perspective of large-scale recognition, millions of these images were annotated and stored in the ImageNet database, fueling the research in visual recognition in the early 2010s. The work of [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], implementing CNNs on GPUs, increased the speed of these algorithms by two orders of magnitude, providing the computational power necessary to learn from large databases. The ImageNet challenge of 2012, where Convolutional Neural Networks outperformed all alternative methods by a wide margin, illustrated a critical point that was reached by data and computational power, inducing a paradigm shift in visual recognition.

In Section 2.4 we describe this paradigm shift that has resulted in the introduction of neural network components in most visual recognition algorithms. First, handcrafted features such as SIFT and their variants were replaced by features extracted from intermediate layers in CNNs (see Chapter 3), leading to major performance improvements. Then, more complex purpose-built architectures were introduced, integrating various steps of processing within unified architectures trained end-to-end.

In parallel, advances in GPU hardware and corresponding software tools have led to increasingly powerful networks and higher performance in real-world applications, effectively democratizing the technology. While our discussion here is focused on visual recognition, these improvements have influenced many fields such as machine translation and speech recognition.

In Section 2.5 we discuss possible paths for future progress, and focus on weaker forms of supervision given the high cost of data annotation. While CNNs are suited for a large number of applications, there are challenges that cannot be addressed yet.

More abstract cases such as image understanding and action recognition in videos remain difficult in real-world scenarios (see Chapter 1) where the complexity of the tasks may exceed our capacity at providing a suitable labeled dataset for learning. Therefore, we are interested in ways to learn from weak forms of supervision (see Chapter 4), using different supervision modalities and possibly, with recent algorithms, without supervision at all (see Chapter 5).

Chapter 3

Learning and Transferring Mid-Level Image Representations using

Convolutional Neural Networks

In this chapter, we address the problem of feature learning and feature generalization across tasks in visual recognition. The procedure described here consists of using a large dataset (the source task ) to build a powerful feature representation for images within a neural network. Then, once this representation is learned, it is applied on a smaller dataset (the target task ) by keeping the learned parameters and the structure of the first processing modules. We bridge the performance gap between

Introduction

Object recognition has been a driving motivation for research in computer vision for many years. Recent progress in the field has allowed recognition to scale up from a few object instances in controlled setups towards hundreds of object categories in arbitrary environments.

Much of this progress has been enabled by the development of robust image descriptors such as SIFT (Lowe [2004a]) and HOG [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]), bag-offeatures image representations [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF], [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF], [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF], [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF]) as well as deformable part models [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]).

Another enabling factor has been the development of increasingly large and realistic image datasets providing object annotation for training and testing, such as Caltech256 [START_REF] Griffin | Caltech-256 object category dataset[END_REF]), Pascal VOC [START_REF] Everingham | The pascal visual object classes (VOC) challenge[END_REF]) and Ima-geNet [START_REF] Deng | ImageNet: A Large-Scale Hierarchical Image Database[END_REF]).

Neural networks for vision. Although they were common before 2012, neural networks have a long history in visual recognition. Rosenblatt's Mark I Perceptron [START_REF] Rosenblatt | The perceptron: A perceiving and recognizing automaton[END_REF]) arguably was one of the first computer vision systems.

Inspired by the neural connectivity pattern discovered by [START_REF] Hubel | Receptive fields of single neurones in the cat's striate cortex[END_REF],

Fukushima's Neocognitron [START_REF] Fukushima | Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position[END_REF]) extended earlier networks with invariance to image translations. But neither Rosenblatt nor Fukushima had the means to train the association layer weights in a supervised manner. This was achieved about a decade later.

Combining the back-propagation algorithm [START_REF] Rumelhart | Learning representations by back-propagating errors[END_REF]) with the Neocognitron architecture, convolutional neural networks [START_REF] Lang | A time delay neural network architecture for speech recognition[END_REF], [START_REF] Lecun | Backpropagation applied to handwritten zip code recognition[END_REF]) quickly achieved excellent results in optical character recognition leading to large-scale industrial applications (LeCun et al. [1998a], [START_REF] Simard | Best practices for convolutional neural networks applied to visual document analysis[END_REF]). Although convolutional networks have been advocated for other vision tasks [START_REF] Vaillant | Original approach for the localisation of objects in images[END_REF], [START_REF] Osadchy | Synergistic face detection and pose estimation with energy-based model[END_REF]) including generic object recognition [START_REF] Lecun | Learning methods for generic object recognition with invariance to pose and lighting[END_REF]), their performance was limited by the relatively small size of the standard object recognition datasets (such as the CalTech and Pascal datasets).

This situation changed with the appearance of the ImageNet dataset [START_REF] Deng | ImageNet: A Large-Scale Hierarchical Image Database[END_REF]) and the rise of GPU computing. Using a very efficient GPU implementation of convolutional neural networks, [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF]) achieve a performance leap in image classification on the ImageNet Large-Scale Visual Recognition Challenge (ILSVRC-2012). Although the challenge calls only for the recognition of 1000 object categories, the best result was achieved using a network trained on the entire ImageNet Fall 2011 release (15 million images, 22000 categories).

Goal: a generic feature transform. The fact that Rosenblatt and Fukushima went ahead without a suitable supervised learning algorithm indicates that they hoped to engineer an effective association layer and reuse this work for a variety of problems.

The remarkable effectiveness of the SIFT features has certainly proven them right for the case of low-level image features. Recent works on scattering transforms [START_REF] Bruna | Invariant scattering convolution networks[END_REF]) provide the means to build mid-level features from first principles.

It is also telling to observe that the early deep learning papers [START_REF] Hinton | Learning multiple layers of representation[END_REF], [START_REF] Hinton | Reducing the dimensionality of data with neural networks[END_REF]) placed the focus on unsupervised learning, and that the convolution kernels learned by the first layer of a convolutional neural network are usually similar to manually engineered edge detectors (see [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], [START_REF] Farabet | Learning hierarchical features for scene labeling[END_REF] for instance).

From this perspective, it seems that supervised learning in a convolutional neural network simply customizes mid-level features for a particular task.

It is therefore natural to investigate under which conditions the features learned by a convolutional neural network on a large dataset can be reused for other computer vision tasks. This contribution reports on experiments carried out by training mid-level features on the ImageNet dataset, which currently is the largest publically available labeled image dataset, and using these features on the Pascal VOC data [START_REF] Everingham | The pascal visual object classes (VOC) challenge[END_REF]), which has sometimes been described as the most challenging current object recognition dataset and therefore the most worthy of interest [START_REF] Torralba | Unbiased look at dataset bias[END_REF]). We focus on the Pascal VOC classification task for ex-pediency reasons: although the system clearly locates the recognized objects in the input image, it does so in a manner that is not immediately suitable for the Pascal VOC detection task.

The issue of image statistics. It has been argued that computer vision datasets have significant differences in image statistics [START_REF] Torralba | Unbiased look at dataset bias[END_REF]).

Transferring CNN weights

The CNN architecture of [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] contains more than 60 million parameters. Directly learning so many parameters from only a few thousand training images is problematic. The key idea of this work is that the internal layers of the

C1-C2-C3-C4-C5 FC 6 FC 7 FC 8
African elephant Wall clock Green snake Yorkshire terrier

Source task

Training images Sliding patches

90

CNN can act as a generic extractor of mid-level image representation, which can be pre-trained on one dataset (the source task, here ImageNet) and then re-used on other target tasks (here object and action classification in Pascal VOC), as illustrated in Figure 3-2. However, this is difficult as the labels and the distribution of images (type of objects, typical viewpoints, imaging conditions, etc.) in the source and target datasets can be very different, as illustrated in Figure 3-3. To address these challenges we (i) design an architecture that explicitly remaps the class labels between the source and target tasks (Section 4.2), and (ii) develop training and test procedures, inspired by sliding window detectors, that explicitly deal with different distributions of object sizes, locations and scene clutter in source and target tasks (Sections 3.2.2 and 4.5).

Network architecture

For the source task, we use the network architecture of [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF]. The network takes as input a square 224 × 224 pixel RGB image and produces a distribution over the ImageNet object classes. This network is composed of five successive convolutional layers C1. . . C5 followed by three fully connected layers FC6. . . FC8

(Figure 3-2, top).
The three fully connected layers compute

Y 6 = 𝜎(W 6 Y 5 + B 6 ) Y 7 = 𝜎(W 7 Y 6 + B 7 ) Y 8 = 𝜓(W 8 Y 7 + B 8 )
where Y 𝑘 denotes the output of the 𝑘-th layer, W 𝑘 , B 𝑘 are the trainable parameters of the 𝑘-th layer,

𝜎(X)[𝑖] = max(0, X[𝑖])
is the ReLU non-linear activation function,

𝜓(X)[𝑖] = 𝑒 X[𝑖] ∑ 𝑗 𝑒 X[𝑗]
is the SoftMax non-linear activation function.

For target tasks (Pascal VOC object and action classification) we wish to design a network that will output scores for target categories, or background if none of the categories are present in the image. However, the object labels in the source task can be very different from the labels in the target task (also called a "label bias" by [START_REF] Torralba | Unbiased look at dataset bias[END_REF]). For example, the source network is trained to recognize different breeds of dogs such as husky dog or australian terrier, but the target task contains only one label dog. The problem becomes even more evident for the target task of action classification. What object categories in ImageNet are related to the target actions reading or running ?

In order to achieve the transfer, we remove the output layer FC8 of the pretrained network and add an adaptation layer formed by two fully connected layers FCa and FCb (see Figure 3-2, bottom) that use the output vector Y 7 of the layer FC7 as input. Note that Y 7 is obtained as a complex non-linear function of potentially all input pixels and may capture mid-level object parts as well as their high-level configurations [START_REF] Le | Building high-level features using large scale unsupervised learning[END_REF], Zeiler et al. [11]). The FCa and FCb layers compute:

Y 𝑎 = 𝜎(W 𝑎 Y 7 + B 𝑎 ) Y 𝑏 = 𝜓(W 𝑏 Y 𝑎 + B 𝑏 )
where W 𝑎 , B 𝑎 , W 𝑏 , B 𝑏 are the trainable parameters.

In all our experiments, FC6 and FC7 have equal sizes (either 4096 or 6144, see

Network training

First, we pre-train the network using the code of [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] Dataset bias issues. As discussed above, the network is pre-trained to classify source task images that depict single centered objects. The images in the target task, however, often depict complex scenes with multiple objects at different scales and orientations with significant amount of background clutter, as illustrated in Figure 3-3 (middle and right). In other words, the distribution of object orientations and sizes as well as, for example, their mutual occlusion patterns is very different between the two tasks. This issue has been also called "a dataset capture bias" by [START_REF] Torralba | Unbiased look at dataset bias[END_REF]. In addition, the target task may contain many other objects in the background that are not present in the source task training data (a "negative data bias" in [START_REF] Torralba | Unbiased look at dataset bias[END_REF]). To explicitly address these issues we train the adaptation layer using a procedure inspired by training sliding window object detectors (e.g. [START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF]) described next. Tiling the image allows matching the average appearance of our source ImageNet 94 dataset for the cars, as shown in Figure 3-6. As a result, we obtain many patches, as shown in Figure 3-7 that we need to label appropriately.

Working our way around dataset bias

Small-scale tiling Large-scale tiling Working our way around dataset bias Note that patch scores could be computed much more efficiently by performing large convolutions on adequately subsampled versions of the full image, as described for instance in [START_REF] Farabet | Learning hierarchical features for scene labeling[END_REF]. This would permit a denser patch coverage at a lower computation cost.

Classification

Experiments

In maps are given in Figures 3-1 and3-9 -3-10. This visualization clearly demonstrates that the system knows the size and locations of target objects within the image.

Addressing the detection task seems within reach, as has been, in parallel to this work, explored with the R-CNN algorithm [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF]). 3.3).

The transfer method significantly improves over the No pretrain baseline where the CNN is trained solely on the action images from Pascal VOC, without pretraining on ImageNet. In particular, we obtain best results on challenging categories playing instrument and taking photo.

In order to better adapt the CNN to the subtleties of the action recognition task, and inspired by Collobert et al. [2011b], our last results were obtained by training the target task CNN without freezing the FC6 weights. More precisely, we copy the ImageNet-trained weights of layers C1. . . C5, FC6 and FC7, we append the adaptation layers FCa and FCb, and we retrain layers FC6, FC7, FCa, and FCb on the action recognition data. This strategy increases the performance on all action categories (row Pre-1512U in Table 3.3), yielding, to the best of our knowledge, the best average result published on the Pascal VOC 2012 action recognition task.

To demonstrate that we can also localize the action in the image, we train the network in a sliding window manner, as described in Section 3.

Conclusion and discussion

Building on the performance leap achieved by [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] on ILSVRC-2012, we have shown how a simple transfer learning procedure yields state-of-the-art results on challenging benchmark datasets of much smaller size. We have also demonstrated the high potential of the mid-level features extracted from an ImageNettrained CNNs. Although the performance of this setup increases when we augment The rightmost column contains the highest-scoring false positive (according to our judgement) for each of these categories. Note that correct estimates of object and action locations and scales are provided by the score maps.

the source task data, using only 12% of the ImageNet corpus already leads to the best published results on the Pascal VOC 2012 classification and action recognition tasks.

Recent developments. This work shows that manually engineered image representations can be outperformed with relative ease using neural networks. Moreover, the performance scales up with data.

Concurrently with this work, other papers showed the generality of CNN features, their potential for learning rich mid-level image features transferrable to a variety of visual recognition tasks, and advocated their wide usage in computer vision. Therefore, this chapter is part of a large body of work following the ImageNet breakthrough of [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], modernizing the field of computer vision by intersecting it with the powerful features of neural networks.

1. [START_REF] Matthew | Visualizing and understanding convolutional networks[END_REF] do an early study of the AlexNet architecture and show the patterns that activate neurons in each layer, sharing their intuitions and understanding on CNNs for the vision community to catch up quickly with the techniques.

2. [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF] use the output of the FC7 layer as a feature vector and connect it to an approach using Selective Search (van de Sande et al. 4. [START_REF] Sermanet | Overfeat: Integrated recognition, localization and detection using convolutional networks[END_REF] propose open-source software for extracting features on images based on their ILSVRC-2013 model.

5. [START_REF] Jia | Caffe: Convolutional architecture for fast feature embedding[END_REF] and [START_REF] Donahue | Decaf: A deep convolutional activation feature for generic visual recognition[END_REF] propose a framework for sharing pre-trained models and using them for feature extraction: the Caffe Model Zoo contains many pre-trained CNN models that helped popularize this technique.

Figure 3-11: In this last example, we show the dog classification score map, and notice that the response is much stronger for a distinctive part such as a front-view of the head, than for the fur. We build on this observation in the next chapter.

Chapter 4

Is object localization for free?

Weakly-supervised learning with convolutional neural networks

In this chapter, we build on an observation from the previous chapter on feature learning and transfer. Heat maps for the dog class in Figure 3-11 (Chapter 3) show that the neural network classifier is more sensitive to the head of a dog than to its fur. We conclude that patches used for training are not equally important for the classification. Based on this observation, in this chapter, we design a method that lets the neural network select that most discriminative patch that results in the best classification performance, demonstrating that the neural networks have naturally strong output on statistically relevant patterns for image classification. We

Introduction

Visual object recognition entails much more than determining whether the image contains instances of certain object categories. For example, each object has a location and a pose; each deformable object has a constellation of parts; and each object can be cropped or partially occluded.

Object recognition algorithms of the 2000s can roughly be categorized in two 110 styles. The first style extracts local image features (SIFT, HOG), constructs bag of visual words representations, and runs statistical classifiers [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF], Perronnin et al. [2010], [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF], [START_REF] Zhang | Local features and kernels for classification of texture and object categories: a comprehensive study[END_REF]). Although this approach has been shown to yield good performance for image classification, attempts to locate the objects using the position of the visual words have been unfruitful: the classifier often relies on visual words that fall in the background and merely describe the context of the object.

The second style of algorithms detects the presence of objects by fitting rich object models such as deformable part models [START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF], [START_REF] Yang | Articulated pose estimation with flexible mixtures-ofparts[END_REF]). The fitting process can reveal useful attributes of objects such as location, pose and constellations of object parts, but the model is usually trained from images with known locations of objects or even their parts. The combination of both styles has shown benefits [START_REF] Harzallah | Combining efficient object localization and image classification[END_REF]).

A third style of algorithms, convolutional neural networks (CNNs, Lang and Hin- [START_REF] Toshev | Deeppose: Human pose estimation via deep neural networks[END_REF]) and others. Most of these methods, however, require detailed image annotation. For example bounding box supervision has been shown highly beneficial for object classification in cluttered and complex scenes (Chapter 3).

The labelling issue. Labelling a set of training images with object attributes quickly becomes problematic. The process is expensive and involves a lot of subtle and possibly ambiguous decisions. For instance, consistently annotating locations and scales of objects by bounding boxes works well for some images but fails for partially occluded and cropped objects. Annotating object parts becomes even harder since the correspondence of parts among images in the same category is often ill-posed.

Goal. In this chapter, we investigate whether CNNs can be trained from complex cluttered scenes labelled only with lists of objects they contain and not their locations.

This is an extremely challenging task as the objects may appear at different locations, different scales and under variety of viewpoints, as illustrated in Figure 4-1 (top row).

Furthermore, the network has to avoid overfitting to the scene clutter co-occurring with objects as, for example, motorbikes often appear on the road. How can we modify the structure of the CNN to learn from such difficult data?

Method. We build on the successful CNN architecture of [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] and the follow-up state-of-the-art results for object classification and detection, but introduce the following modifications.

1. We treat the last fully connected network layers as convolutions to cope with the uncertainty in object localization.

2. We introduce a max-pooling layer that hypothesizes the possible location of the object in the image, similar to [Lang et al., 1990, Section 4] and [START_REF] Keeler | Integrated segmentation and recognition of hand-printed numerals[END_REF].

3. We modify the cost function to learn from image-level supervision.

Interestingly, we find that this modified CNN architecture, while trained to output We find that our weakly-supervised network

• outputs accurate image-level labels,

• predicts approximate locations (but not extents) of objects, and

• performs comparably to its fully-supervised counterparts that use object bounding box annotation for training.

Architecture for weakly supervised learning

We build on the fully supervised network architecture described in Chapter 3, that consists of five convolutional and four fully connected layers and assumes as input a fixed-size image patch containing a single relatively tightly cropped object. To adapt this architecture to weakly supervised learning we introduce the following three modifications.

Convolutional adaptation layers

The network architecture of Chapter 3 assumes a fixed-size image patch of 224×224

RGB pixels as input and outputs a 1 × 1 × 𝐾 vector of per-class scores as output,

where 𝐾 is the number of classes. The aim is to apply the network to bigger images in a sliding window manner thus extending its output to 𝑛 × 𝑚 × 𝐾 where 𝑛 and 𝑚 denote the number of sliding window positions in the 𝑥-and 𝑦-direction in the image, respectively, computing the 𝐾 per-class scores at all input window positions.

While this type of sliding was performed in Chapter 3 by applying the network to independently extracted image patches, here we achieve the same effect by treating the fully connected adaptation layers as convolutions. For a given input image size, the fully connected layer can be seen as a special case of a convolution layer where the size of the kernel is equal to the size of the layer input. With this procedure the output of the final adaptation layer FC7 becomes a 2 × 2 × 𝐾 output score map for a 256 × 256 RGB input image.

As the global stride of the network is 32 1 pixels, adding 32 pixels to the image

Explicit search for object's position via max-pooling

The aim is to output a single image-level score for each of the object classes independently of the input image size. This is achieved by aggregating the 𝑛 × 𝑚 × 𝐾 matrix of output scores for 𝑛 × 𝑚 different positions of the input window using a global maxpooling operation into a single 1 × 1 × 𝐾 vector, where 𝐾 is the number of classes.

Note that the max-pooling operation effectively searches for the best-scoring candidate object position within the image, which is crucial for weakly supervised learning where the exact position of the object within the image is not given at training. In addition, due to the max-pooling operation the output of the network becomes independent of the size of the input image, which will be used for multi-scale learning in Section 4.3.

Multi-label classification loss function

The goal of object classification is to tell whether an instance of an object class is present in the image, where the input image may depict multiple different objects.

As a result, the usual multi-class mutually exclusive logistic regression loss, as used in e.g. [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] for ImageNet classification, is not suited for this set-up as it assumes only a single object per image. To address this issue, we treat the task as

𝑃 (𝑘|x) ≈ 1 1 + 𝑒 -𝑓 𝑘 (x) . (4.2)
Treating a multi-label classification problem as k independent classification problems is often inadequate because it does not model label correlations. This is not an issue here because the classifiers share hidden layers and therefore are not independent.

Such a network can model label correlations by tuning the overlap of the hidden state distribution given each label.

Weakly supervised learning and classification

In

Stochastic gradient descent with global max-pooling

The global max-pooling operation ensures that the training error backpropagates only to the network weights corresponding to the highest-scoring window in the image. In other words, the max-pooling operation hypothesizes the location of the object in the image at the position with the maximum score, as illustrated in Figure 4-4. If the image-level label is positive (i.e. the image contains the object) the back-propagated error will adapt the network weights so that the score of this particular window (and hence other similar-looking windows in the dataset) is increased. On the other hand, if the image-level label is negative (i.e. the image does not contain the object) the backpropagated error adapts the network weights so that the score of the highest-scoring window (and hence other similar-looking windows in the dataset) is decreased.

For negative images, the max-pooling operation acts in a similar manner to hardnegative mining known to work well in training sliding window object detectors [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]).

Note that there is no guarantee the location of the score maxima corresponds to the true location of the object in the image. However, the intuition is that the erroneous weight updates from the incorrectly localized objects will only have limited effect as in general they should not be consistent over the dataset.

Multi-scale sliding-window training

The above procedure assumes that the object scale (the size in pixels) is known and the input image is rescaled so that the object occupies an area that corresponds to the receptive field of the fully connected network layers (i.e. 224 pixels).

In general, however, the actual object size in the image is unknown. In fact, a single image can contain several different objects of different sizes. One possible solution would be to run multiple parallel networks for different image scales that share parameters and max-pool their outputs. We opt for a different less memory demanding solution.

Instead, we train from images rescaled to multiple different sizes. The intuition is that if the object appears at the correct scale, the max-pooling operation correctly localizes the object in the image and correctly updates the network weights. When the object appears at the wrong scale the location of the maximum score may be incorrect. As discussed above, the network weight updates from incorrectly localized objects may only have limited negative effect on the results in practice.

In detail, all training images are first rescaled to have the largest side of size 500 pixels and zero-padded to 500 × 500 pixels. Each training mini-batch of 16 images is then resized by a scale factor 𝑠 uniformly sampled between 0.7 and 1.4. This allows the network to see objects in the image at various scales. In addition, this type of multi-scale training also induces some scale-invariance in the network.

Classification

At test time we apply the same sliding window procedure at multiple finely sampled scales. In detail, the test image is first normalized to have its largest dimension equal to 500 pixels, padded by zeros to 500 × 500 pixels and then rescaled by a factor 𝑠 ∈ {0.5, 0.7, 1, 1.4, 2.0, 2.8}. Scanning the image at large scales allows the network to find even very small objects. For each scale, the per-class scores are computed for all window positions and then max-pooled across the image.

These raw per-class scores (before applying the soft-max function (4.2)) are then aggregated across all scales by averaging them into a single vector of per-class scores.

The testing architecture is illustrated in Figure 4-3. We found that searching over only six different scales at test time was sufficient to achieve good classification performance. Adding wider or finer search over scale did not bring additional benefits in our experiments.

Implementation details

Our training architecture (Figure 4-2) relies on max-pooling the outputs of the convolutional network operating on a small batch of potentially large images. Several implementation details make this possible.

• In order to accomodate images of various sizes, all network layers are implemented as convolutions. Layers that were described as fully connected layers in [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] are also viewed as convolutions (see Figure 4-2.)

• The GPU convolution code decomposes each convolution into an intricate sequence of cuBLAS 2 calls on adequately padded copies of the input image and kernel weights. Unlike previous "unfolded" convolution approaches [START_REF] Chellapilla | High performance convolutional neural networks for document processing[END_REF]), our scheme does not make multiple copies of the same input pixels and therefore consumes an amount of GPU memory comparable to that of the image itself. This implementation runs at least as fast as that of [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] without relying on large mini-batches and without consuming extra memory. This allows for larger images and larger networks. CuDNN, written by nVidia since, offers a faster and more memory efficient implementation of the convolution operation, rendering this code obsolete today.

• The training code performs fast bilinear image scaling using the GPU texture units3 . This is used for resizing the input images with random scales at training time.

• All the adaptation layers use dropout [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF]). However, instead of zeroing the output of single neurons, we zero whole feature maps with probability 50% in order to decorrelate the gradients across different maps and prevent the coadaptation of the learned features. This variant of Dropout is now known as SpatialDropout and commonly available in CNN frameworks.

Our implementation takes the form of additional packages for the Torch7 environment.4

Classification experiments

In this section we describe our classification experiments where we wish to predict whether the object is present / absent in the image. Predicting the location of the object is evaluated in section 4.6. 3 . c a r : 7 4 .6 4 . m o to r c y c le : 8 0 .9 5 . a ir p la n e : 8 8 .9 6 . b u s : 7 3 .9 7 . tr a in : 8 6 .2 8 . tr u c k : 5 8 .8 9 . b o a t : 7 3 .1 1 0 . tr a ff ic li g h t : 7 0 .0 1 1 . fi r e h y d r a n t : 6 1 .9 1 3 . s to p s ig n : 6 5 .1 1 4 . p a r k in g m e te r : 4 7 .9

Location prediction experiments

The proposed weakly supervised architecture outputs score maps for different objects.

In the previous section we have shown that max-pooling on these maps provides excellent classification performance. However, we have also observed that these scores maps are consistent with the locations of objects in the input images. In this section we investigate whether the output score maps can be used to localize the objects.

Experiments

Location prediction metric. In order to provide quantitative evaluation of the localization power of our CNN architecture, we introduce a simple metric based on precision-recall using the per-class response maps. We first rescale the maps to the original image size5 . If the maximal response across scales falls within the ground truth bounding box of an object of the same class within 18 pixels tolerance (which corresponds to the pooling ratio of the network), we label the predicted location as correct. If not, then we count the response as a false positive (it hit the background), and we also increment the false negative count (no object was found). Finally, we use the confidence values of the responses to generate precision-recall curves. Each p-r curve is summarized by Average Precision (AP). The perfect performance (AP=1) means that the network has indicated the presence / absence of the object correctly in all images and for each image containing the object the predicted object location tion performance to the strong R-CNN baseline, which uses object bounding boxes at training time.

Discussion

Does adding object-level supervision help location prediction? Here we investigate whether adding the object-level supervision (with masked pooling) helps to better predict the locations of objects in the image. The results on the Pascal VOC dataset are shown in Table 4.3 and show a very similar overall performance for our weakly supervised (j.Weak sup) method compared to the object-level supervised (i.Masked pool) setup. This is interesting as it indicates that our weakly supervised method learns to predict object locations and adding object-level supervision does not significantly increase the overall location prediction performance. Results on the COCO dataset are shown in Figure 4-5 (bottom) and indicate that for some classes with poor location prediction performance in the weakly supervised setup (green) adding object-level supervision (masked pooling, magenta) helps. Examples are small sports objects such as frisbee, tennis racket, baseball bat, snowboard, sports ball, or skis. While for classification the likely presence of these objects can be inferred from the scene context, object-level supervision can help to understand better the underlying concept and predict the object location in the image. We examine the importance of the object context next.

The importance of object context. To better assess the importance of object context for the COCO dataset we directly compare the classification (blue) and location prediction (green) scores in Figure 4-5 (middle). In this setup a high classification score but low location prediction score means that the classification decision was taken primarily based on the object context. Fore example, the presence of a baseball field is a strong indicator for presence of a baseball bat and a baseball glove. However, as discussed above these objects are hard to localize in the image. The kitchenware (forks, knives, spoons) and electronics (laptop, keyboard, mouse) superclasses show a similar behavior. Nevertheless, a good classification result can still be informative and can guide a more precise search for these objects in the image.

Predicting extent of objects. To evaluate the ability to predict the extent of objects (not just the location) we also evaluate our method using the standard area overlap ratio as used in object detection [START_REF] Everingham | The pascal visual object classes (VOC) challenge[END_REF]). We have implemented a simple extension of our method that aggregates CNN scores within selective search (van de Sande et al. [2011]) object proposals. This procedure obtains on the Pascal VOC 2012 validation set the mAP of 11. 74, 27.47, 43.54% for area overlap thresholds 0.5, 0.3, 0.1, respectively. The relatively low performance could be attributed to (a) the focus of the network on discriminative object parts (e.g. aeroplane propeller, as in Figure 4-4) rather than the entire extent of an object and (b) no max-pooling over scales in our current training procedure. Similar behavior on discriminative parts was recently observed in scene classification by [START_REF] Zhou | Object Detectors Emerge in Deep Scene CNNs[END_REF].

Conclusion of this chapter

So, is object localization with convolutional neural networks for free? We have shown that our weakly supervised CNN architecture learns to predict the location of objects in images despite being trained from cluttered scenes with only weak image-level labels.

We believe this is possible because of (i) the hierarchical convolutional structure of CNNs that appears to have a bias towards spatial localization combined with (ii) the extremely efficient end-to-end training that back-propagates loss gradients from image-level labels to candidate object locations.

While the approximate position of objects can be predicted rather reliably, this is not true (at least with the current architecture) for the extent of objects as the network tends to focus on distinctive object parts.

In particular, we show that for classification, taking a decision based on the context of an object (such as a kitchen for determining the presence of knives, forks, spoons without locating them properly) corresponds to the idea that statistically relevant patterns are considered by the algorithm to provide a prediction.

We believe our results are significant as they open-up the possibility of large-scale reasoning about object relations and extents without the need for detailed object level annotations.

Recent developments. The work presented in this chapter is part of a body of work that attempts to run CNNs as sliding window classifiers on images larger than the base receptive field, collecting maps as output. One of the earliest popular incarnations of this idea is the work of [START_REF] Sermanet | Overfeat: Integrated recognition, localization and detection using convolutional networks[END_REF], integrating a localization and detection pipeline within a neural network for the ILSVRC-2013 competition using strong bounding-box supervision.

The sliding approach was later largely explored in the object segmentation problem, notably in the work of [START_REF] Pedro O Pinheiro | Learning to segment object candidates[END_REF] and [START_REF] Long | Fully convolutional networks for semantic segmentation[END_REF] where CNNs are used to compute segmentation maps for objects in images in end-to-end setups.

The work of [START_REF] Zhou | Object Detectors Emerge in Deep Scene CNNs[END_REF] confirms our findings in this chapter in a scene classification setup, noticing that objects that are statistically relevant for a given scene consistently activate specific parts of the inner layers of the CNN allowing to perform interpretable object localization.

Weakly supervised object localization was further pursued notably in the work of [START_REF] Bilen | Weakly supervised deep detection networks[END_REF] or our own work [START_REF] Kantorov | Contextlocnet: Context-aware deep network models for weakly supervised localization[END_REF]) adressing the object detection task that requires also predicting the extent of objects. Chapter 5

Unsupervised learning with CNNs

In the previous chapters, we presented methods for supervised learning of image representation for object classification. But as discussed in Chapter 1, if we want to build a general visual recognizer, then supervised learning may not be a good approach, as it is difficult to provide enough annotated data for training. We saw in Chapter 4 that neural networks will naturally focus on the statistical regularities that appear in the data, in particular patterns correlated with a given class, that we need to provide in quantities large enough for the algorithms to learn properly.

For supervised classification tasks, current methods typically deploy the following strategy: (i) collect as much data as possible, (ii) train a neural net. But if direct actions (such as use+knife+onion) are to be recognized by a pattern recognition system such as a neural network, then we have the following issue: while it is already difficult and costly to annotate thousands of object classes, the supervised approach scales even worse for combinations of objects, properties and their relations, such as "person on a chair", "girl playing tennis", or "blue van".

However, once we step away from the supervised path, it is not clear what method should be applied. Different directions are being explored, such as for example reinforcement learning [START_REF] Richard | Reinforcement learning: An introduction[END_REF]), which lets software agents interact with an environment giving it sparse rewards, and learn to take actions that maximize the reward over time; in this chapter we are interested in the path of unsupervised learning, which should let algorithms learn from large amounts of unlabeled data. Un-supervised learning is the Holy Grail of machine learning: the idea that an algorithm could observe the world and capture its regularities on its own, without any help from humans, is a driving force for researchers eager to build Artificial Intelligence.

Introduction

Unsupervised learning as a way to extract knowledge from unlabeled data remains largely unsolved. At this time, the potential of unsupervised learning is not known, and it is a matter of belief whether this could help in solving hard problems such as those based on understanding the content of an image or video (as described in Chapter 1). The belief in this idea stems from the fact that the human brain is able to learn and study new things in an autonomous way, without a teacher explaining what is presented to us at every step and providing supervision. Therefore, there should be conditions where it should be possible for a machine to learn without external help, and we believe finding such conditions is an interesting long-term research goal.

One major issue in this research direction is that problems are not properly defined, as they are not related to a specific task or benchmark. Currently, unsupervised algorithms are indirectly evaluated (such as e.g. learning a feature transform from unsupervised data then evaluating its performance in an object detection pipeline as proposed by [START_REF] Doersch | Unsupervised visual representation learning by context prediction[END_REF]), or sometimes not evaluated beyond qualitative observations. Therefore, in contrast with the previous chapters, the focus of this work on unsupervised learning is more on collecting knowledge and insights than delivering task-oriented results. This field is not mature yet and problems still need to be framed; so far the general idea is mostly to seek ways to extract knowledge from data by observing it.

In the following, we give a high-level overview of the content of this chapter, starting with (i) a review of generative adversarial networks (GANs) as a new approach for unsupervised learning, (ii) difficulties with their evaluation, (iii) links between GANs and causality, and finally (iv) understanding cost functions optimized by GANs.

Figure 5-1: Left: Faces reconstructed using the variational autoencoder approach described in [START_REF] Diederik | Auto-encoding variational bayes[END_REF]. Right: Faces generated by a Deep Convolutional Generative Adversarial Network [START_REF] Radford | Unsupervised representation learning with deep convolutional generative adversarial networks[END_REF]). Images credit: Alec Radford.

Unsupervised learning with GANs. Attempts at unsupervised learning in computer vision were made in earlier work, notably with the use of clustering algorithms such as K-means to build sparse dictionaries [START_REF] Leung | Representing and recognizing the visual appearance of materials using three-dimensional textons[END_REF], [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF]) or algorithms for topic modeling used in the text literature [START_REF] Sivic | Discovering object categories in image collections[END_REF]). In the particular case of neural networks, unsupervised learning was first addressed with autoencoder architectures, introduced by Rumelhart et al. [1986],

where the goal is to first map an input to a lower-dimensional code (encoding phase) using an encoder network, then to reconstruct the initial input from the code (decoding phase) using a decoder network; the intuition is that frequent patterns in the data should be stored in a way similar to a dictionary in the networks, allowing a compressed representation of the input as a code 1 . Autoencoders are usually trained using an objective function (e.g. the squared difference) comparing the initial input and the reconstruction obtained by decoding. However, the training procedure can experimentally result in smooth blurry reconstructions, as shown in Figure 5-1. Recently, Generative Adversarial Networks (GANs) were proposed by [START_REF] Goodfellow | Generative adversarial nets[END_REF], and are actively studied as of 2017. GANs are able to generate sharper, crisper images than autoencoders (see 1 Additional references on autoencoders are provided in Chapter 2.

Figure 5-1), reviving interest in unsupervised learning using neural networks. Given the major successes achieved in the supervised scenario, hopes and expectations have been set high for this new unsupervised incarnation of neural networks.

In contrast to autoencoders, the GAN training procedure does not rely on reconstructing specific examples and therefore does not depend explicit formulation of the reconstruction loss; instead, a generator network generates random images, and a discriminator evaluates whether these generated images look similar to those of a reference dataset, using only a binary classification objective to provide gradient to the generator. This has practical applications in supervised variants of GANs, as the discriminator approach eliminates the need to specify a loss function: new tasks can be defined implicitly using only data (e.g. [START_REF] Isola | Image-to-image translation with conditional adversarial networks[END_REF], see Figure 5-4). We start this chapter by giving an overview of GANs in Section 5.2 to understand their underlying principle, and show examples of applications in vision.

Evaluating GANs. As a result of their training, GANs are able to generate images from a distribution 𝑝 𝑔 learned by observing real reference data that follows a distribution 𝑝 𝑑𝑎𝑡𝑎 . Running a GAN generator provides new samples, but no estimate of the probability of a given sample: this excludes using maximum likelihood estimation of samples under a GAN model. How to evaluate GANs? In Section 5.3 we investigate this problem, and inspired by the role played by the discriminator we propose applying a statistical two-sample test approach to evaluate a GAN model and evaluate whether the distributions 𝑝 𝑔 and 𝑝 𝑑𝑎𝑡𝑎 match. While our method does not solve the general evaluation problem, it allows performing a first level of model selection.

Links between GANs and causality.

Interested in what could be missing elements in order to engineer a setup capable of intelligent high-level reasoning, following the work of Lopez-Paz [2016] we are interested in links between GANs and causal reasoning. Can GANs learn causal relations from data? Harnessing causality would allow inferring the state of a system under hypothetical manipulations. Being able to answer a question such as "what would happen if... ?" seems closely related to predicting possible future outcomes and understanding the links between different elements of a dynamic scene. This is better illustrated by the example in [START_REF] Bottou | From machine learning to machine reasoning[END_REF]: rain and umbrellas are generally correlated, but causal reasoning adds the idea that banning umbrellas will not stop the rain.

While it seems possible to learn such links in an interventional scenario by performing an action and observing consequences, we are interested in understanding cause-effect relationships from only observational data, more readily available. To illustrate this, we take the example of a marionette, shown in Figure 5-9: the body of the marionette hangs below a plate, held by strings. Is it possible, using only observations, for a machine to understand that the position of the plate is the cause and the position of the body is the effect ?

In Section 5.4, we connect GANs to the subject of causality. First, we design a synthetic setup inspired by marionettes that we expect to contain a causal component. While we believe the problem is worthy of study, obtaining results proved difficult. Yet, looking for a way to extract causal information using GANs, we combine them with two-sample tests for the task of cause-effect discovery in a more successful approach, obtaining competitive results on the Tüebingen cause-effect pairs dataset.

Cost functions of GANs. In our last part, in Section 5.5, we are interested in the properties of the distribution 𝑝 𝑔 . What is learned by GANs? Building on recent contributions formalizing this issue and a connection to optimal transport, we expose the depth of this problem that appears, finally, to be much more subtle than minimizing a Jensen-Shannon divergence as suggested in the initial GAN paper by [START_REF] Goodfellow | Generative adversarial nets[END_REF]. Although it relates to the difficult problem of defining a similarity function between images, the goal of this section is to advocate the study of such distance metrics in order to understand the behavior and the output of these algorithms more clearly.

Review of Generative Adversarial Networks

Overview

Generative adversarial networks [START_REF] Goodfellow | Generative adversarial nets[END_REF]) are a recent idea in the field of neural networks, where the goal is to train a generative model allowing easy generation of new samples resembling a source dataset.

The GAN model, shown in figure 5-2 is composed of a generator neural network and a discriminator neural network working together on a reference (real ) dataset.

The generator takes random vectors as input and generates fake images using deconvolution layers that increase the resolution of data at each stage of the neural network.

The discriminator (a common CNN) then tries to discriminate between fake images produced and real images by solving a binary classification problem.

Since the discriminator is differentiable, it can produce gradient indicating what small changes should be applied to the generated images for them to look more real to the discriminator. Using this gradient, the generator adapts its parameters. Training GANs helps the generator in producing increasingly realistic synthetic images which are harder to distinguish from real images by the discriminator.

Alternating between generation and discrimination appears like a game played by two adversaries, hence the name of the technique. GANs implement the adversarial loss function defined below:

min 𝑔 max 𝑑 E 𝑥∼𝑃 (𝒳 ) [log(𝑑(𝑥))] + E 𝑧∼𝑃 (𝒵) [log(1 -𝑑(𝑔(𝑧)))] , (5.1)
where 𝑑(𝑥) denotes the probability of the example 𝑥 following the data distribution 𝑃 (𝒳 ) versus being synthesized by the generator. This is according to a trainable discriminator function 𝑑.

In the adversarial game, the generator 𝑔 plays to fool the discriminator 𝑑 by transforming noise vectors 𝑧 ∼ 𝑃 (𝒵) into real-looking examples 𝑔(𝑧). On the opposite side, the discriminator plays to distinguish between real examples 𝑥 and synthesized examples 𝑔(𝑧). To approximate the solution to (5.1), we alternate optimization of the two losses [START_REF] Goodfellow | Generative adversarial nets[END_REF] given by

𝐿 𝑑 (𝑑) = E 𝑥∼𝑃 (𝒳 ) [ℓ(𝑑(𝑥), 1)] + E 𝑧∼𝑃 (𝒵) [ℓ(𝑑(𝑔(𝑧)), 0)] , 𝐿 𝑔 (𝑔) = E 𝑥∼𝑃 (𝒳 ) [ℓ(𝑑(𝑥), 0)] + E 𝑧∼𝑃 (𝒵) [ℓ(𝑑(𝑔(𝑧)), 1)] . (5.2)
With (5.2), the adversarial game reduces to the sequential minimization of 𝐿 𝑑 (𝑑) and 𝐿 𝑔 (𝑔) where ℓ is a binary classification loss function. The discriminator optimizes the loss 𝐿 𝑑 (𝑑), in order to predict a positive (1) label for real samples 𝑥 and negative (0) label for fake samples 𝑔(𝑧). The generator adapts accordingly by optimizing the loss 𝐿 𝑔 (𝑔). As a result, the generator trained with this procedure is able to sample from a distribution 𝑝 𝑔 = 𝑔(𝒵) that is close to 𝑝 𝑑𝑎𝑡𝑎 according to the discriminator network 𝑑.

The GAN approach proposed in 2014, therefore, describes a viable approach to 139 build a generative model that allows sampling from a distribution resembling a reference data distribution, without the need to write a loss function explicitly: the loss function between the generated samples and the real samples is implicitly defined by the discriminator. This method has been actively studied since 2014 as we show next.

Applications of GANs

As an example of the work on GANs, the LAPGANs2 (Denton et al. As a result, given a condition 𝑐 the generator produces a corresponding relevant image 𝑥. Many setups in computer vision (e.g. [START_REF] Isola | Image-to-image translation with conditional adversarial networks[END_REF], [START_REF] Zhu | Generative visual manipulation on the natural image manifold[END_REF]) leverage this approach (see Figure 5-4) and show visually appealing generated samples. We will notably use this variant in Section 5.4 for causal discovery.

The challenge of evaluating GANs

In the context of GANs, the whole discriminator can be seen as a loss function providing gradient to the generative model; the binary classification loss of the discriminator is not very informative indeed. Not relying on explicit loss functions has an important consequence: there is no clear method for evaluation.

As a result of their training, GANs are able to generate samples following a a distribution 𝑝 𝑔 . The goal is for 𝑝 𝑔 to be as close as possible to the data distribution 𝑝 𝑑𝑎𝑡𝑎 .

But using only samples from these distributions, measuring the distance between 𝑝 𝑔 and 𝑝 𝑑𝑎𝑡𝑎 is difficult as mentioned in [START_REF] Theis | A note on the evaluation of generative models[END_REF]. In particular, the authors mention that there is no universal metric of how well a distribution fits, and each metric involves its tradeoffs, as illustrated in Figure 5-16 (Section 5.3). Because of this issue, it is difficult to measure improvements on this class of algorithms. However, alternatives were proposed; for example, [START_REF] Salimans | Improved techniques for training GANs[END_REF] propose the inception score: using a classification network to measure the entropy of the distribution of the output predictions. While they report good correlation with human crowdsourced evaluation, the justification remains empirical. Alternatively, the performance of GANs can be evaluated indirectly on surrogate tasks, such as super-resolution which consists of increasing the resolution of an image, with corresponding performance metrics available, as proposed by [START_REF] Ledig | Photo-realistic single image super-resolution using a generative adversarial network[END_REF].

In Section 5.3, we propose an evaluation procedure based on a statistical twosample test with the following intuition: if the sample distribution produced by the generator is close to the reference data distribution, then the associated binary classification problem should be difficult. We explore this direction and obtain mixed results, revealing generation artifacts in the process.

Evaluating GANs

In this section, we propose to use a binary classification setup to compare whether two distributions are similar or not. The underlying intuition is: if two distributions are close, then binary classification whether a new point is coming from one of the two distributions should be difficult. We apply this approach to GANs that we trained using the procedure from [START_REF] Radford | Unsupervised representation learning with deep convolutional generative adversarial networks[END_REF], in an attempt to evaluate the sample quality from our models.

Though one could use the binary classification result directly to provide a ranking of GAN models, in this section we provide a statistical interpretation of this result to connect it to two-sample tests between samples. Moreover, the statistical two-sample test point-of-view allows us to use the Maximum Mean Discrepancy two-sample test of [START_REF] Gretton | A kernel two-sample test[END_REF] for this evaluation problem.

The evaluation problem with GANs

GANs build generator functions that are able to generate samples from random noise vectors. However, they do not allow retrieving the likelihood value 𝑝(𝑥) of a real data sample 𝑥, therefore usual approaches such as Maximum Likelihood Estimation can not be applied. Similarly, auto-encoder approaches can be evaluated on the quality of reconstructions for a given sample; but in the case of GANs, there is no specific target to reconstruct, excluding this approach as well.

The examples proposed in the DCGAN work of [START_REF] Radford | Unsupervised representation learning with deep convolutional generative adversarial networks[END_REF] (see Figure 5-3) hint at three possible approaches for empirical evaluation of a generator.

The first approach is to assess the visual quality of generated samples. This is usually done by observing samples qualitatively, but there is currently no way to systematically evaluate this criterion except by crowdsourcing perceptual evaluation e.g. in Amazon Mechanical Turk, as done in [START_REF] Isola | Image-to-image translation with conditional adversarial networks[END_REF] and [START_REF] Zhu | Generative visual manipulation on the natural image manifold[END_REF].

The second one consists of observing whether the generating function 𝑔 learned by the GAN corresponds to a continuous mapping. This can be done by generating samples from points along a segment [𝑧 1 , 𝑧 2 ] in input space 𝒵 and observing whether the resulting samples in image space 𝒳 correspond to a meaningful interpolation. We illustrate this method with our pendulums experiment, as we describe in Section 5.4, Figure 5-14, confirming this property of the generator.

The third one is to verify whether the model allows for performing arithmetics on the problem, as illustrated in Figure 5-3 (bottom), which should be evidence for an even stronger model, where the representation in latent noise space disentangles modes of variation in the data. These two approaches, interpolation and arithmetics, are meaningful in specific cases like faces, for which we have attributes that are sometimes continuous (e.g. smiling or frowning have continuous ranges). In the general case of images where the presence or absence of an object is a discrete variable, these modes of variation are not clearly defined.

These three approaches require manual observation of the resulting images. In the following, we propose a two-sample testing approach on the real data and the generated distributions, and observe that the computed test statistic value correlates with the visual quality of images.

Two-sample tests

The goal of two-sample tests is to assess whether two samples, denoted by 𝑆 𝑃 ∼ 𝑃 𝑛 and 𝑆 𝑄 ∼ 𝑄 𝑚 , are drawn from the same distribution [START_REF] Lehmann | Testing statistical hypotheses[END_REF].

More specifically, two-sample tests either accept or reject the null hypothesis, often denoted by 𝐻 0 , which stands for "𝑃 = 𝑄". When rejecting 𝐻 0 , we say that the twosample test favors the alternative hypothesis, often denoted by 𝐻 1 , which stands for "𝑃 ̸ = 𝑄". To accept or reject 𝐻 0 , two-sample tests summarize the differences between the two samples (sets of identically and independently distributed examples):

𝑆 𝑃 := {𝑥 1 , . . . , 𝑥 𝑛 } ∼ 𝑃 𝑛 (𝑋) and 𝑆 𝑄 := {𝑦 1 , . . . , 𝑦 𝑚 } ∼ 𝑄 𝑚 (𝑌 ) (5.3) into a statistic t ∈ R. Without loss of generality, we assume that the two-sample test returns a small statistic when the null hypothesis "𝑃 = 𝑄" is true, and a large statistic otherwise. Then, for a sufficiently small statistic, the two-sample test will accept 𝐻 0 . Conversely, for a sufficiently large statistic, the two-sample test will reject 𝐻 0 in favour of 𝐻 1 .

More formally, the statistician performs a two-sample test in four steps. First, decide a significance level 𝛼 ∈ [0, 1], which is an input to the two-sample test. Second, compute the two-sample test statistic t. Third, compute the p-value p = 𝑃 (𝑇 ≥ t|𝐻 0 ), the probability of the two-sample test returning a statistic as large as t when 𝐻 0 is true. Fourth, reject 𝐻 0 if p < 𝛼, and accept it otherwise.

With classifiers. Without loss of generality, we assume access to the two samples 𝑆 𝑃 and 𝑆 𝑄 defined in (5.3), where 𝑥 𝑖 , 𝑦 𝑗 ∈ 𝒳 , for all 𝑖 = 1, . . . , 𝑛 and 𝑗 = 1, . . . , 𝑚,

and 𝑚 = 𝑛. To test whether the null hypothesis 𝐻 0 : 𝑃 = 𝑄 is true, we proceed in five steps.

First, we construct the binary classification dataset

𝒟 = {(𝑥 𝑖 , 0)} 𝑛 𝑖=1 ∪ {(𝑦 𝑖 , 1)} 𝑛 𝑖=1 =: {(𝑧 𝑖 , 𝑙 𝑖 )} 2𝑛 𝑖=1 .
Second, we shuffle 𝒟 at random, and split it into the disjoint training and testing subsets 𝒟 tr and 𝒟 te , where 𝒟 = 𝒟 tr ∪ 𝒟 te and 𝑛 te := |𝒟 te |.

Third, we train a binary classifier 𝑓 : 𝒳 → [0, 1] on 𝒟 tr ; in the following, we assume that 𝑓 (𝑧 𝑖 ) is an estimate of the conditional probability distribution 𝑝(𝑙 𝑖 = 1|𝑧 𝑖 ).

Fourth, we return the classification accuracy on 𝒟 te :

t = 1 𝑛 te ∑ (𝑧 𝑖 ,𝑙 𝑖 )∈𝒟te I [ I ( 𝑓 (𝑧 𝑖 ) > 1 2 ) = 𝑙 𝑖 ] (5.4)
as our C2ST statistic, where I is the indicator function. The intuition here is that if 𝑃 = 𝑄, the test accuracy (5.4) should remain near chance-level. In opposition, if 𝑃 ̸ = 𝑄 and the binary classifier unveils distributional differences between the two samples, the test classification accuracy (5.4) should be greater than chance-level.

Fifth, to accept or reject the null hypothesis, we compute a p-value using the null distribution of the C2ST statistic t and compare it to the significance level 𝛼. We study below the distribution of t under the null hypothesis 𝐻 0 : 𝑃 = 𝑄, and under the alternative hypothesis 𝐻 1 : 𝑃 ̸ = 𝑄.

Null Distribution. Each term I [I(𝑓 (𝑧 𝑖 ) > 1/2) = 𝑙 𝑖 ] appearing in (5.4) is an independent Bernoulli(𝑝 𝑖 ) random variable, where 𝑝 𝑖 is the probability of classifying correctly the example 𝑧 𝑖 in 𝒟 te .

Under the null hypothesis 𝐻 0 : 𝑃 = 𝑄, the samples 𝑆 𝑃 ∼ 𝑃 𝑛 and 𝑆 𝑄 ∼ 𝑄 𝑚 follow the same distribution, leading to an impossible binary classification problem.

In that case, 𝑛 te t follows a Binomial(𝑛 te , 𝑝 = 1 2 ) distribution. Therefore, for large 𝑛 te , we can use the central limit theorem to approximate the null distribution of (5.4) by

𝒩 ( 1 2 , 1 4𝑛 te
).

The cumulative distribution function (CDF) of the test statistic distribution then lets us compute the corresponding p-value to accept or reject the hypothesis from a statistical perspective by comparing it to the significance level 𝛼. For ranking GAN models however, this thresholding step is not necessary.

Results

We obtain state-of-the-art performance for two-sample tests using our approach against alternative approaches such as the Maximum Mean Discrepancy (MMD) criterion proposed by [START_REF] Gretton | A kernel two-sample test[END_REF], validating this approach as described in detail in Lopez-Paz and [START_REF] Lopez-Paz | Revisiting classifier two-sample tests[END_REF]; for clarity, in this chapter we focus only on the use of two-sample tests for model selection in the context of GANs. To this end, we train a number of DCGANs on the bedroom class of LSUN [START_REF] Yu | Lsun: Construction of a large-scale image dataset using deep learning with humans in the loop[END_REF]) and the Labeled Faces in the Wild (LFW) dataset [START_REF] Huang | Labeled faces in the wild: A database for studying face recognition in unconstrained environments[END_REF]). We reused the Torch7 code of [START_REF] Radford | Unsupervised representation learning with deep convolutional generative adversarial networks[END_REF] to train a set of DCGANs for {1, 10, 50, 100, 200} epochs, where the generator and discriminator networks are 4-layer deep convolutional neural networks with variable numbers of filters; we describe the architectures in detail in Appendix C.

Then, in order to perform evaluation for each generator, we generate 10, 000 samples, and use 10, 000 held-out real data samples to build our two-sample test dataset.

This dataset is then shuffled and split into a training set and a testing set for the classification procedure.

Artifacts. Our first experiments reveal an interesting result. When performing two-sample tests directly on pixels using a classifier with an architecture identical to the one of discriminator, we obtain near-perfect test accuracy when distinguishing between real and synthesized (fake) examples. Such near-perfect accuracy happens consistently across DCGANs, regardless of the visual quality of their examples.

To explain this, we propose two possible hypotheses. The first is that there is overlap between the training and testing sets obtained with the generator, which would correspond to the issue of "mode collapse" reported in concurrent work (e.g. [START_REF] Metz | Unrolled generative adversarial networks[END_REF]), where the generator outputs only a small discrete set of samples.

Our second hypothesis is that the generated samples contain a signature of the generation process such that they are easy to recognize by a classifier. This is because, albeit visually appealing, the fake examples contain checkerboard-like artifacts that may be sufficient for the tests to consistently differentiate between real and fake examples. Odena et al. [2016] observed this phenomenon concurrently with us, as they show in Figure 5-5. We show in Figure 5-6 that even when an image looks visually acceptable to the human eye, observing the output of the first layer of a CNN may still reveal heavy checkerboard artifacts.

Results on featurized images. In order to alleviate the possible issues mentioned above, on a second series of experiments, we featurize all images (both real and fake) using a deep convolutional ResNet [START_REF] He | Deep residual learning for image recognition[END_REF]) pre-trained on ImageNet. In particular, we use the output of the last fully-connected layer of the resnet-34 model from [START_REF] Gross | Training and investigating residual nets[END_REF] to obtain feature vectors of dimensionality 2048. We then perform the following two-sample tests:

• Linear-time estimate of the Maximum Mean Discrepancy (MMD, Gretton et al.

[2012], [START_REF] Jitkrittum | Interpretable distribution features with maximum testing power[END_REF]) with Radial Basis Function kernels.

• C2ST-NN: this corresponds to the classifier two-sample test procedure described in 5.3.2, where the classifier is a two-layer fully-connected neural network with 148 20 hidden units and a ReLU non-linearity. We choose a small number of units to have a classifier with reasonable training time, and use the Adam optimizer (Kingma and Ba [2015a]) for 100 epochs to reach convergence in all our experiments.

• C2ST-KNN: this classifier two-sample test is based on a K-nearest neighbor classifier with 𝐾 = √ |𝒟 𝑡𝑒 |, which is the standard "rule-of-thumb value" for these classifiers.

Reusing a CNN model pre-trained on natural images ensures that the test will distinguish between real and fake examples based only on natural image statistics, such as Gabor filters, edge detectors, and so on. Such a strategy is similar to perceptual losses (Johnson et al. [2016]) and inception scores [START_REF] Salimans | Improved techniques for training GANs[END_REF]). In short, in order to evaluate how natural the images synthesized by a DCGAN look, we employ a "natural discriminator". Figure 5-7 shows three GANs producing poor samples and three GANs producing good samples for the LSUN [START_REF] Yu | Lsun: Construction of a large-scale image dataset using deep learning with humans in the loop[END_REF]) and Labeled Faces in the Wild (LFW) [START_REF] Huang | Labeled faces in the wild: A database for studying face recognition in unconstrained environments[END_REF]) datasets, according to the MMD, C2ST-KNN, C2ST-NN tests on top of ResNet features.

Assessing the reliability of this test is difficult, as the quality of samples is prone to human judgement. However we believe this procedure can help in filtering out the worst cases, allowing a level of model selection in an automated way. In particular, "collapsed" generators, that only output a small discrete set of images, can be detected easily because of the overlap between the training and testing sets of the classifier two-sample test.

Conclusion of this section

In this section, we develop the idea of evaluating GAN models with two-sample tests, and propose an approach based on classifiers. We show that the test statistic distribution can be approximated under the null hypothesis 𝐻 0 : 𝑃 = 𝑄, making it a viable statistical two-sample test.

We apply this approach to sets of images generated by GANs with a classifier of random sample MMD KNN NN 0.158 0.830 0.999 0.154 0.994 1.000 0.048 0.962 1.000 0.012 0.798 0.964 0.024 0.748 0.949 0.019 0.670 0.983 0.152 0.940 1.000 0.222 0.978 1.000 0.715 1.000 1.000 0.015 0.817 0.987 0.020 0.784 0.950 0.024 0.697 0.971

Figure 5-7: Results on GAN evaluation. The six first (resp. last) rows correspond to GAN models trained on the LSUN bedrooms (resp. LFW ) dataset. We show samples from the models with the best and worst test statistic for each two-sample test that we used (MMD, C2ST-NN and C2ST-KNN). Lower test statistics are best and appear to correlate with better sample quality. We provide more detailed examples in the Appendix C. The typical values are specific to each two-sample test method; with C2ST (columns KNN and NN), the test statistic corresponds to the test set accuracy, and we note that the neural network classifier has very high performance in all cases: the task remains too easy for this classifier in this setup. The KNN classifier, on the other hand, has a wider range of accuracy values, making its results easier to use for model selection. same architecture as the discriminator but systematically obtain perfect classification results. Further observation of images shows the presence of artifacts due to the network architectures that are involved, sometimes even invisible to the human eye.

One hypothesis is that the presence of these artifacts makes it extremely easy for a classifier to discriminate between fake samples and real samples when trained directly on the pixels. This also highlights that in GAN training, discriminators are in general powerful enough to win the adversarial game every time given enough training steps, and one key to the success of GAN training is to cripple the discriminator, either by not training it completely (which corresponds to the algorithm proposed initially) or regularizing it; one popular method, described in [START_REF] Arjovsky | To appear in ICML[END_REF], consists of penalizing or constraining its Lipschitz constant to achieve this goal.

These artifacts also show that GANs are able to generate samples but with limitations due to the restriction of the function set defined by the architectures of the networks involved and/or the learning procedures; they carry (at least) a signature of the generation process.

In the case of images featurized by a transform learned on natural images, this issue is of much lesser extent, and this leads to an evaluation method with a test value that correlates with the visual quality of samples. The underlying justification is that a feature transform learned on natural images should not be sensitive to the generation artifacts observed in fake samples. This approach helps in filtering out the worst cases when training many GANs, allowing a level of model selection.

Causality and physics

In this section, we are interested in introducing concepts from causality to generative adversarial networks.

First, we illustrate this problem with the physical behaviour of a marionette. In this case, the problem has a causal structure: the position of the plate is the cause, and the position of the body below is the effect. The work of Lopez-Paz et al. [2017] advocates the presence of a causal signal in images, and we are interested in whether a GAN can capture this structure. The setup that we describe in 5.4.1, however, was not able to capture this global structure in our data. We performed an experiment on a simpler dataset generated with a similar procedure, and observed that a GAN is able to learn a good representation if the data is simpler; therefore we believe this marionette problem can be addressed in the future with better and more stable GAN algorithms.

Second, we investigate the related subproblem of causal discovery using twosample tests in 5.4.2. Causal discovery aims at finding, given a set of pairs of data (𝑥 𝑖 , 𝑦 𝑖 ) whether 𝑥 corresponds to the cause and 𝑦 to the effect, or vice versa. This subproblem is relevant to the marionette, as in this case one variable could correspond to the position of the plate, and the other variable to the position of a limb.

We propose a setup based on the conditional variant of GANs, conditioning on one of the variables to generate the other, and build on the idea that it should be easier to generate an effect from a cause than the other way around. We evaluate this setup on the Tübingen cause-effect pairs dataset ( [START_REF] Mooij | Distinguishing cause from effect using observational data: methods and benchmarks[END_REF]).

Statistical footprints of causality. Lopez-Paz et al. [2017] build on the idea that causal signals carry a statistical footprint due to the assumption that for a causal process such that 𝑋 → 𝑌 ("𝑋 causes 𝑌 "), the cause (represented by the distribution 𝑃 (𝑋)) and the mechanism mapping the cause to the effect (represented by 𝑃 (𝑌 |𝑋))

are independent. This is called the Independance between Cause and Mechanism (ICM) assumption and is described in [START_REF] Schölkopf | On causal and anticausal learning[END_REF].

This assumption is illustrated better in the case of an Additive Noise Model : we consider the case 𝑌 ← 𝑓 (𝑋) + 𝐸, where 𝑋 and 𝐸 are independent uniform variables, and 𝑓 is a linear function. We show plots in Figure 5-8. In this case the causal direction 𝑌 → 𝑋 would violate the ICM assumption: we observe that under this hypothesis the variance of the noise depends on 𝑌 . Therefore the causal direction 𝑋 → 𝑌 is preferred.

These detectable footprints are likely to be many and in order to avoid building a corresponding catalog, Lopez-Paz et al. [2017] propose to learn these footprints from data, and predict a neural causation coefficient (NCC) to bags of samples (𝑥 𝑖 , 𝑦 𝑖 ) 𝑖 .

One research direction of interest is recovering such a causal signal in observational data such as in the setup that we describe below.

Marionette physics

GANs are promising algorithms and examples hint that they are capturing structure in the data without supervision (e.g. [START_REF] Radford | Unsupervised representation learning with deep convolutional generative adversarial networks[END_REF], shown in Figure 5-3 or [START_REF] Sun | Pronet: Learning to propose object-specific boxes for cascaded neural networks[END_REF]). In this context, we made a first attempt at extracting physical structure from a synthetic dataset that we designed, inspired by marionettes, as shown in Figure 56789. Concurrent work demonstrated interest in learning physics from visual observations [START_REF] Mottaghi | Newtonian scene understanding: Unfolding the dynamics of objects in static images[END_REF]) and in an unsupervised scenario with GANs ( [START_REF] Fragkiadaki | Learning visual predictive models of physics for playing billiards[END_REF]), which gave us inspiration for this setup.

The idea behind marionettes is that physical constraints apply to the position of the limbs depending on the position of the plate in a causal manner, up to some noise depending on the past positions and momentum. As such, we expect the set of appearances of a marionette and its plate to lie on a small subset of the image space, and we expect this set to be small enough for its structure to be captured by a generative model.

Using a physics engine. In concurrent work related to problems involving physics, the contribution of Lerer et al. [2016] proved particularly useful. The authors notably build an interface between a game engine (the open-source Unreal Engine 4 (UE4)) and the machine learning framework Torch7 (Collobert et al. [2011a]). Game engines are useful in this context because they are optimized for rendering increasingly realistic images in real-time. Moreover, they usually include a physics simulation engine for scenes to look more natural, making them useful for synthetizing data.

We build a puppet mesh and rig it using the 3D design software Blender. A mesh defines the appearance of a 3D object. Rigging a mesh consists of associating subsets Figure 5-10: Left: our puppet model. Right: the corresponding solid bodies for physical simulation. Constraints appear between pairs of connected bodies, restricting the possible motions. Each bone in the armature is approximated with a primitive called body that has a simple shape, a mass and a volume; examples include spheres, cubes, cylinders and capsules. Bodies are connected to each other by physical constraints defining the range of motion that is permitted, and other physical properties such as friction.

of the mesh to bones connected within a skeleton, or armature. This allows animating a mesh; by simply moving the armature, the associated vertices of the mesh follow.

Then, we add physical properties to our puppet in the Physics tool of UE4 as shown in Figure 5-10.

Simulating the puppet. We connect our puppet to a plate using strings, with the head fixed, and move the plate randomly in terms of angle and speed, collecting screenshots regularly. We obtain the dataset shown in Figure 5-11.

We expect the data to follow a model similar to an Additive Noise Model: body position = 𝑓 𝑝ℎ𝑦𝑠𝑖𝑐𝑠 (plate) + noise, (5.5)

where the noise depends on past momentum and positions of the body (physical inertia). We run a DCGAN algorithm on this data using the code of Radford et al.

[2016] and obtain the results described next. While the puppet experiment corresponds for now to a negative result, we believe the setup remains interesting because of the presence of a global structure in the example images. Moreover, this work may possibly be improved in the future with more stable GAN models and procedures.

A simpler setup. Here we do an additional experiment to show that a simpler synthetic dataset can be learned properly by a GAN. We build such a dataset using the physics simulator. In this data, two red pendulums hang below a blue bar, attached with green bars. The data is shown in Figure 5-13. A DCGAN generator trained on this simpler data learns the data in a way that allows meaningful interpolation in the latent space 𝒵 between samples, as we show in Figure 5-14. Therefore, a GAN is able to build a continuous generative model based on multiple observations of a given object, confirming that this work could be revisited with GAN algorithms able to deal with more complex details such as those of the puppet.

But it is yet unclear if our interest in GANs -whether we can extract the causal structure of this physical setup -is founded. We investigate this question next, and look for causal signals with GANs.

Figure 5-13: Our simpler pendulums dataset, built with the physics engine of UE4, consists of two red pendulums hanging below a randomly moving blue plate. The pendulums can move in all three dimensions.

Figure 5-14: Results of interpolation in the noise space after training a DCGAN on the pendulums dataset. In each case, we interpolate between the leftmost and the rightmost samples. The model learns a continuous mapping between the latent space and the image space.

Cause-effect discovery with two-sample tests

The GAN approach to retrieve causal structure from our physics simulation has not been successful yet, but there is still hope, and we keep looking for a way to capture a causal signal from data using GANs. To this end, in this part we use GANs for the simpler setup of causal discovery, using the two-sample test procedure described in Section 5.3.

Problem definition.

In causal discovery, we study the causal structure underlying a set of 𝑑 random variables 𝑋 1 , . . . , 𝑋 𝑑 . In particular, we assume that random variables 𝑋 1 , . . . , 𝑋 𝑑 share a causal structure described by a collection of Structural Equations, or SEs [START_REF] Pearl | Causality[END_REF]). More specifically, we assume that for all 𝑖 = 1, . . . , 𝑑, the random variable 𝑋 𝑖 takes values as described by the SE: The goal of causal discovery is to infer the causal graph 𝒢 given a sample from 𝑃 (𝑋 1 , . . . , 𝑋 𝑑 ). For the sake of simplicity, we focus on the discovery of causal relations between two random variables, denoted by 𝑋 and 𝑌 . In particular, this setup excludes the case where 𝑋 and 𝑌 are the effects of a common cause. Given the sample 𝒟 = {(𝑥 𝑖 , 𝑦 𝑖 )} 𝑛 𝑖=1 ∼ 𝑃 𝑛 (𝑋, 𝑌 ), our goal is to conclude whether "𝑋 causes 𝑌 ", or "𝑌 causes 𝑋". We call this problem cause-effect discovery [START_REF] Mooij | Distinguishing cause from effect using observational data: methods and benchmarks[END_REF]. In the case where 𝑋 → 𝑌 , we can write the cause-effect relationship as: 𝑥 ∼ 𝑃 (𝑋), 𝑛 ∼ 𝑃 (𝑁 ), 𝑦 ← 𝑔(𝑥, 𝑛).

𝑋 𝑖 = 𝑔 𝑖 (
(5.7)

The current state-of-the-art in the cause-effect discovery is the family of Additive Noise Models, or ANM [START_REF] Mooij | Distinguishing cause from effect using observational data: methods and benchmarks[END_REF]. These methods assume that the SE (5.7) allow the expression 𝑦 ← 𝑔(𝑥) + 𝑛, and exploit the independence assumption between the cause random variable 𝑋 and the noise random variable 𝑁 to analyze the distribution of nonlinear regression residuals, in both causal directions.

Proposed method. Assuming independent additive noise is often too simplistic (for instance, the noise could be heteroskedastic or multiplicative). Because of this reason, we propose to use Conditional Generative Adversarial Networks, or CGANs [START_REF] Mirza | Conditional generative adversarial nets[END_REF] to address the problem of cause-effect discovery. Our motivation is the resemblance between the generator of a CGAN and the SE (5.7):

the random variable 𝑋 is the conditioning variable input to the generator, the random variable 𝑁 is the noise variable input to the generator, and the random variable 𝑌 is the variable synthesized by the generator. Furthermore, CGANs respect the independence between the cause 𝑋 and the noise 𝑁 by construction, since 𝑛 ∼ 𝑃 (𝑁 )

is independent from all other variables. This way, CGANs bypass the additive noise assumption naturally, and allow arbitrary interactions 𝑔(𝑋, 𝑁 ) between the cause variable 𝑋 and the noise variable 𝑁 .

To implement our cause-effect inference algorithm in practice, recall that training a CGAN from 𝑋 to 𝑌 minimizes the two following objectives in alternation:

𝐿 𝑑 (𝑑) = E 𝑥,𝑦 [ℓ(𝑑(𝑥, 𝑦), 1)] + E 𝑥,𝑧 [ℓ(𝑑(𝑥, 𝑔(𝑥, 𝑧)), 0)] , 𝐿 𝑔 (𝑔) = E 𝑥,𝑦 [ℓ(𝑑(𝑥, 𝑦), 0)] + E 𝑥,𝑧 [ℓ(𝑑(𝑥, 𝑔(𝑥, 𝑧)), 1)] . (5.8)
where ℓ is a binary classification loss function, 𝑑 is the discriminator function and 𝑔(𝑥, 𝑧) is a sample from the generator conditioned on 𝑥, using the latent vector 𝑧.

The discriminator optimizes the loss 𝐿 𝑑 (𝑑), in order to predict a positive (1) label for real samples ((𝑥, 𝑦)) and negative (0) label for fake samples (𝑥, 𝑔(𝑥, 𝑧)). The generator adapts accordingly by optimizing the loss 𝐿 𝑔 (𝑔).

Our recipe for cause-effect is to learn two CGANs: one with a generator 𝑔 𝑦 from 𝑋 to 𝑌 to synthesize the dataset 𝒟 𝑋→𝑌 = {(𝑥 𝑖 , 𝑔 𝑦 (𝑥 𝑖 , 𝑧 𝑖 ))} 𝑛 𝑖=1 , and one with a generator 𝑔 𝑥 from 𝑌 to 𝑋 to synthesize the dataset 𝒟 𝑋←𝑌 = {(𝑔 𝑥 (𝑦 𝑖 , 𝑧 𝑖 ), 𝑦 𝑖 )} 𝑛 𝑖=1 . Then, we prefer the causal direction 𝑋 → 𝑌 if the two-sample test statistic (Equation (5.4), Section 5.3) between the real sample 𝒟 and 𝒟 𝑋→𝑌 is smaller than the one between 𝒟 and 𝒟 𝑌 →𝑋 . Thus, our method CGAN-C2ST is Occam's razor at play: declare the simplest direction (in terms of conditional generative modeling) as the true causal direction. Results. Table 5.1 summarizes the performance of this procedure when applied to the 99 Tübingen cause-effect pairs dataset, version August 2016 [START_REF] Mooij | Distinguishing cause from effect using observational data: methods and benchmarks[END_REF].

This dataset corresponds to hand-collected real-world cause-effect samples from 99 different causal phenomena such as e.g. (altitude → temperature) or (age → salary)

where the ground truth causal direction is decided by expert knowledge after studying the data-generating mechanism; this dataset of real samples is therefore small because of this tedious collection process. We show examples of this data in Figure 5-15.

The proposed method Ensemble-CGAN-C2ST trains, for each causal phenomenon, 100 CGANs in each direction as explained in the previous paragraph. Then, for each CGAN, we run a Classifier Two-Sample Test (C2ST, described in Section 5.3) to evaluate the quality of the new generated samples. Finally, we compare the C2ST statistics (equation (5.4)) of the best generator in each causal direction to predict the causal direction 𝑋 → 𝑌 or 𝑋 ← 𝑌 .

We obtain competitive results with the CGAN-C2ST approach and outperform the state-of-the-art result of Lopez-Paz et al. [2017] (NCC, 79%) by using an ensemble of 100 CGANs. The need to ensemble is a remainder of the unstable behaviour of generative adversarial training, but also highlights the promise of such models for causal discovery.

Conclusion of this section

In this section, we were interested in the usage of Generative Adversarial Networks to recover causal signals from data. In the first part we described an experiment based on a synthetic dataset built using a physics engine, that, we expect, carries a causal component in its global structure. Learning this data using a GAN proved difficult and the generated samples did not carry the causal structure; the hope is that better GAN algorithms may be able to learn the underlying model of this data in the future.

In the second part we address the problem of cause-effect discovery; this simple case corresponds to a basic building block for causal inference, that consists of determining in a dataset of causally-related pairs (𝑥 𝑖 , 𝑦 𝑖 ) 𝑖 , whether X causes Y or Y causes X. We proposed the usage of the conditional variant of GANs combined with the two-sample tests described in Section 5.3, showing promising results on the Tübingen cause-effect pairs dataset. In this last section, our goal is to investigate different distance metrics between two distributions for GAN training. Matching two distributions, as in the GAN context, prompts for a distance to evaluate how well the generated distribution 𝑝 𝑔 fits the data distribution 𝑝 𝑑𝑎𝑡𝑎 . Regarding this issue, [START_REF] Theis | A note on the evaluation of generative models[END_REF] report on an example, shown in Figure 5-16, that optimizing different distances leads to different solutions when trying to fit data with a model. In a related work, [START_REF] Nowozin | f-GAN: Training generative neural samplers using variational divergence minimization[END_REF] explore the optimization of "generative neural samplers" using different objectives.

Distances between distributions

This shows that (i) it should be possible to optimize GANs in different ways and (ii)

this should lead to different solutions.

Therefore we are interested in how GANs are optimized and look for insights on what is the generated distribution that is learned. In the following, we investigate three distance measures between distributions, namely the popular Kullback-Leibler divergence (KL), the Jensen-Shannon divergence (JS, which is connected to GANs) and the Earth Mover Distance (EMD, which is connected to the new Wasserstein-GAN algorithm of [START_REF] Arjovsky | To appear in ICML[END_REF]).

Definitions

Kullback-Leibler (KL) Divergence. The KL divergence between distributions P (the data) and Q (the model) is the amount of information (from the information theory point of view) that is needed to rebuild the distribution P from the distribution Q. It is defined as :

𝐾𝐿(𝑃 ||𝑄) = ∫ 𝑃 (𝑥)𝑙𝑜𝑔 ( 𝑃 (𝑥) 𝑄(𝑥)
) 𝑑𝑥.

(5.9)

If 𝑃 (𝑥) > 0 and 𝑄(𝑥) = 0 over a non-negligible region of the space (i.e. there is data that is not covered by the model) then 𝐾𝐿(𝑃 ||𝑄) = +∞.

Jensen-Shannon (JS) Divergence. The JS divergence between P (the data) and Q (the model) is a symmetrical distance built using the KL divergence. It is defined as:

𝐽𝑆(𝑃 ||𝑄) = 𝐽𝑆(𝑄||𝑃 ) = 1 2 ( 𝐾𝐿 ( 𝑃 || 𝑃 + 𝑄 2 ) + 𝐾𝐿 ( 𝑄|| 𝑃 + 𝑄 2 )) .
(5.10)

If there is no overlap at all between the distributions P and Q, then we obtain 𝐽𝑆(𝑃 ||𝑄) = log 2, which is the maximal value of the JS divergence. In particular in the case of GANs, [START_REF] Goodfellow | Generative adversarial nets[END_REF] show that under the assumption that the discriminator is perfectly trained at each step, the globally optimal solution for the training objective of the generator (Equation (5.1)) minimizes the JS divergence. In practice however, GAN implementations do not minimize the training objective (5.1) but instead alternately optimize of the two losses in (5.2) (see Section 5.2).

Earth Mover Distance (Wasserstein-1). The Earth Mover Distance is defined formally as the 𝑝 = 1 case of the general p-th Wasserstein distance :

𝑊 𝑝 (𝑃, 𝑄) = 𝑖𝑛𝑓 𝛾∈Γ(𝑃,𝑄) (∫ 𝒳 ×𝒳 𝑑(𝑥, 𝑦) 𝑝 d𝛾(𝑥, 𝑦) ) 1/𝑝 (5.11)
where Γ(𝑃, 𝑄) is the set of all joint probability distributions (or couplings) that have P and Q as marginals, and 𝑑(𝑥, 𝑦) is a metric on the corresponding sample space 𝒳 .

The EMD is a distance between two distributions P and Q that can be intuitively seen in the following way: if P and Q correspond to piles of dirt in a space 𝒳 , and work corresponds to the mass of dirt × how far it is moved, then the EMD is the total work needed to transform P into Q, if dirt is moved optimally: it is the cost of the optimal transport plan. We build the intuition from the formal definition in (5.11)

with the following scenario: let points 𝑥 be suppliers in a group 𝑃 , each producing a mass 𝑝(𝑥) with a total sum of 1 and points 𝑦 consumers in a group 𝑄, each requiring a mass 𝑞(𝑦), also summing to 1.

By definition, we have ∫ 𝒳 𝛾(𝑥, 𝑦) d𝑥 = 𝑞(𝑦). This means that each point 𝑦 obtains its total mass 𝑞(𝑦) by receiving 𝛾(𝑥, 𝑦) units from each point 𝑥. By definition, we also have ∫ 𝒳 𝛾(𝑥, 𝑦) d𝑦 = 𝑝(𝑥). This means that each point 𝑥 distributes all its mass 𝑝(𝑥) by sending 𝛾(𝑥, 𝑦) units to each point 𝑦.

This defines a transport plan 𝛾 from 𝑃 to 𝑄, mapping the suppliers 𝑥 to the consumers 𝑦. We now introduce the cost 𝑑(𝑥, 𝑦) of transporting a unit of mass from 𝑥 to 𝑦. Minimizing the integral in (5.11) searches the least expensive transport plan from 𝑃 to 𝑄 according to the metric function 𝑑, i.e. how to move the mass optimally.

We show an example of EMD in Figure 5-17 below.

Figure 5-17: Example of optimal transport on a 32 × 32 grid. Left: density of the distribution P. Middle: density of Q with the optimal transport plan overlaid. Right: optimal transport plan. Each colored line corresponds to the displacement of the mass from one point to another. In this simple case, all points in the supports of P and Q have the same mass. The Earth Mover Distance corresponds to the sum of the cost of individual contributions to the transport plan.

The Wasserstein distance uses a metric function 𝑑 over pairs of points in 𝒳 , and generalizes it to pairs of probability distributions having support in 𝒳 . In contrast to KL and JS, it does not require overlap between the distributions but builds on the notion of ground distance instead.

In vision, [START_REF] Rubner | The earth mover's distance as a metric for image retrieval[END_REF] advocate its use for image retrieval, by computing Earth Mover Distances between distributions (histograms) of features (color, texture) extracted from images. In particular, the Wasserstein-GAN training algorithm of [START_REF] Arjovsky | To appear in ICML[END_REF] builds on this distance to stabilize GAN learning.

Toy experiments

We conduct toy experiments in order to gain better understanding of the distances between distributions mentioned above. In these experiments the goal is to fit a model to a set of data points sampled from a square non-uniform distribution. Additional details are provided in Appendix D.

In Figure 5-19 we show the density of this square distribution (left); we sample points (middle) and estimate their density with a Kernel Density Estimation method (right). We then define a parameterized model as a uniform probability distribution, with the shape of a rectangle, with three parameters: height, width, and rotation angle, shown in Figure 5-18. We observe that the Maximum Likelihood method attemps to cover all the points, where the EMD method is less sensitive to points with low density.

Estimated density Kullback-Leibler Jensen-Shannon EMD Colormap

Figure 5-21: We fit the uniform rectangle to the estimated density by minimizing the KL, JS and EMD distances. EMD is computed using Euclidean distance on the 2D plane. The KL method will attempt to cover all the density, where the JS and EMD methods are able to ignore some points, fitting the dense areas with higher values.

the sampled points by optimizing the Maximum Likelihood under the model, and the Earth Mover Distance. In Figure 5-21 we show our second experiment: we fit the model to the density estimate, by optimizing the Kullback-Leibler divergence, the Jensen-Shannon divergence, and the Earth Mover Distance.

We get the following insights from running this experiment: KL and JS require overlap between densities (and therefore smoothing the data with density estimation);

while optimizing KL will attempt to cover all the data, JS is able to ignore samples and make tradeoffs. This implicitly regularizes the solutions, preferring ones with better density estimates in the overlapping areas4 . EMD, on the other hand, does not require overlap but a ground distance function; as a result, the penalty for not covering a sample is proportional to the distance, and our experiments suggest that this allows better capturing the general shape of the data, by spreading outliers around the model evenly according to the ground distance.

Discussion

JS in original GAN. The initial work of [START_REF] Goodfellow | Generative adversarial nets[END_REF] uses the JS divergence to prove that the global minimum for its training procedure, when the generator distribution matches the data distribution, is 𝑝 𝑔 = 𝑝 𝑑𝑎𝑡𝑎 under the assumptions that:

1. the discriminator is perfectly trained at each step; this poses a problem because the slope of the binary classification loss function should be zero under this assumption.

2. the underlying neural network architecture is able to represent 𝑝 𝑑𝑎𝑡𝑎 ; the proposed justification is the excellent performance of neural networks in practice.

The GAN training procedure depends on gradient provided by the discriminator in order to train the generator, and the first assumption is violated in practice. As a result of this approximation, gradient is obtained, and the generator is adjusted according to this signal that we expect to depend on the architecture and state of the discriminator in unknown ways.

In Section 5.3 we observed that generated samples often contain artifacts, and this means that the second assumption could be wrong in the case of images. Moreover, while it is possible to generate samples that look good to the human eye, artifacts can still appear in the upper layers of a network, as we show in Figure 5-6; better architectures are likely to alleviate this issue, but it may be useful to keep in mind that the generation process can carry a signature from its synthetic nature.

The neural net distance. What is learned? [START_REF] Arora | Generalization and equilibrium in generative adversarial nets (gans)[END_REF] propose to formalize this problem with the notion of ℱ-divergence. ℱ corresponds to a restriction of the set of functions (which would correspond to a network architecture) and implicitly carries the properties of the discriminator:

Let ℱ be a class of functions from R 𝑑 to [0, 1] and 𝜑 be a concave measuring function from [0, 1] to R. Then the ℱ-divergence with respect to 𝜑 between two distributions 𝑃 and 𝑄 supported on R 𝑑 is defined as

𝑑 ℱ ,𝜑 (𝑃, 𝑄) = sup 𝑓 ∈ℱ |E 𝑥∼𝑃 [𝜑(𝑓 (𝑥))] + E 𝑥∼𝑄 [𝜑(1 -𝑓 (𝑥))]| -2𝜑(1/2) (5.12)
In Equation 5.12, 𝑓 ∈ ℱ corresponds to a classifier function discriminating between samples from 𝑃 and 𝑄. If 𝜑 is the logarithm function, then the first (resp. second)

term is the classification loss on samples from 𝑃 (resp. 𝑄). A perfect classifier should output 𝑓 (𝑥 ∼ 𝑃 ) = 1 and 𝑓 (𝑥 ∼ 𝑄) = 0. If no classifier 𝑓 ∈ ℱ can discriminate between samples from 𝑃 and 𝑄, we have 𝑓 (𝑥) = 1/2, and the third term ensures that the ℱ-divergence becomes 0. The ℱ-divergence measures whether a set of functions ℱ is "blind" to the differences between two distributions P and Q; it notably exposes the role of architecture, that defines the set ℱ.

When 𝜑(𝑡) = 𝑙𝑜𝑔(𝑡) and ℱ is the set of all functions from R 𝑑 to [0, 1] then 𝑑 ℱ ,𝜑 (𝑃, 𝑄) = 2 𝐽𝑆(𝑃 ||𝑄). And in this particular case, we can observe that minimizing 𝑑 ℱ ,𝜑 (𝑃, 𝑄) with respect to Q corresponds to Equation 5.1, which is the initial GAN objective of [START_REF] Goodfellow | Generative adversarial nets[END_REF]. We derive this JS divergence below.

Deriving the JS divergence. We first note that for (𝑎, 𝑏) ∈ R 2 ∖ {0, 0}, the

function 𝑦 ↦ → 𝑎 log(𝑦) + 𝑏 log(1 -𝑦) is maximal for 𝑦 = 𝑎 𝑎 + 𝑏
. Then we continue with the following derivation5 :

𝑑 ℱ ,𝜑 (𝑃, 𝑄) = sup 𝑓 ∈ℱ [E 𝑥∼𝑃 [ log(𝑓 (𝑥))] + E 𝑥∼𝑄 [ log(1 -𝑓 (𝑥))]] -2 log(1/2) (5.13) = sup 𝑓 ∈ℱ [∫ 𝑥 𝑝(𝑥) log(𝑓 (𝑥))𝑑𝑥 + ∫ 𝑥 𝑞(𝑥) log(1 -𝑓 (𝑥))𝑑𝑥 ] -2 log(1/2) (5.14) = ∫ 𝑥 𝑝(𝑥) log ( 𝑝(𝑥) 𝑝(𝑥) + 𝑞(𝑥) ) 𝑑𝑥 + ∫ 𝑥 𝑞(𝑥) log ( 𝑞(𝑥) 𝑝(𝑥) + 𝑞(𝑥) ) 𝑑𝑥 -2 log(1/2) (5.15) = 𝐾𝐿 ( 𝑃 || 𝑃 + 𝑄 2 ) + log(1/2) + 𝐾𝐿 ( 𝑄|| 𝑃 + 𝑄 2 ) + log(1/2) -2 log(1/2) (5.16) = 2 𝐽𝑆(𝑃 ||𝑄) (5.17)
We retrieve the JS divergence because ℱ is the set of all functions and 𝑓 can therefore reach the optimal function 𝑥 ↦ → 𝑝(𝑥) 𝑝(𝑥) + 𝑞(𝑥) .

However if ℱ is a function set restricted by an architecture, such as in practice with GAN discriminators, then this optimal function cannot be reached in general;

the properties of the corresponding ℱ-divergence are not clear and minimizing it, as done by the GAN procedure, should not correspond to minimizing the JS divergence in the general case. This notion of ℱ-divergence proposed by [START_REF] Arora | Generalization and equilibrium in generative adversarial nets (gans)[END_REF] exposes the subtlety of the distance that is minimized between these distributions when training a GAN, as it depends on the architecture that restricts the set ℱ.

Wasserstein-GAN and optimal transport. [START_REF] Arjovsky | To appear in ICML[END_REF] propose a different abstraction of this problem by building on a connection with optimal transport in an algorithm called Wasserstein-GAN (WGAN). This method consists of imposing a Lipschitz constraint on the discriminator, building on the Kantorovitch-Rubinstein dual formulation [START_REF] Villani | Optimal transport: old and new[END_REF]) of the 𝑊 1 distance:

𝑊 1 (𝑃, 𝑄) = 𝑠𝑢𝑝 ||𝑓 || 𝐿 ≤1 E 𝑥∼𝑃 [𝑓 (𝑥)] -E 𝑥∼𝑄 [𝑓 (𝑥)] .
(5.18)

The formulation (5.18) fits in the ℱ-divergence formulation (5.12) as pointed out by [START_REF] Arora | Generalization and equilibrium in generative adversarial nets (gans)[END_REF], it is the case where 𝜑(𝑥) = 𝑥 and ℱ = {𝑓 : ||𝑓 || 𝐿 ≤ 1}.

In this equation (5.18), 𝑓 corresponds to a potential function assigning values to the samples and varying slowly because of the 1-Lipschitz (||𝑓 || 𝐿 ≤ 1) constraint. The intuition is that maximizing this expression with respect to 𝑓 consists of assigning higher values to samples of 𝑃 and lower values to those of 𝑄; because of the upperbounded variations (due to the Lipschitz constraint6 ), this maximal difference in potential is proportional to the distance between samples from the optimal coupling.

Moreover, using expectations adds a linear dependency to the mass, prioritizing dense areas and allowing tradeoffs (being robust to outliers) during maximization. In the case where 𝑃 = 𝑄, we have 𝑊 1 (𝑃, 𝑄) = 0. We retrieve the intuition on the Earth Mover Distance described previously, as this function grows linearly with the distance between samples of 𝑃 and 𝑄, with a linear dependency to mass, and reaching 0 when the distributions are the same.

Implementation in WGAN. The WGAN algorithm implements the dual formulation (5.18) in the following loss function:

𝑊 1 (𝑝 𝑑𝑎𝑡𝑎 , 𝑝 𝑔 ) = 𝑠𝑢𝑝 ||𝑓 || 𝐿 ≤1 E 𝑥∼𝑝 𝑑𝑎𝑡𝑎 [𝑓 (𝑥)] -E 𝑧∼𝒵 [𝑓 (𝑔(𝑧))] , (5.19)
where 𝑓 is now called the "critic" (playing a role similar to the discriminator) and 𝑔 is the generator. The procedure then involves three operations.

First, the critic 𝑓 is restricted to be in a set of convolutional networks that are K-Lipschitz, by constraining all weights to a box [-𝑚, +𝑚], with 𝑚 ∈ R and approximately minimizing the equivalent objective 𝐾.𝑊 17 .

changed: it is therefore Lipschitz-continuous wrt. the pixelwise L 2 metric. The point of view of optimal transport hints at the following question: can we define and optimize with another metric function 𝑑, in order to control the learning better and extract information in an unsupervised way?

Conclusion of this section

In this section, we focus on the subject of distances between distributions, as GANs allow matching a generated distribution 𝑝 𝑔 with a data distribution 𝑝 𝑑𝑎𝑡𝑎 . While the initial formulation of [START_REF] Goodfellow | Generative adversarial nets[END_REF] proposes a link with the minimization of the JS divergence, recent insights from [START_REF] Arjovsky | To appear in ICML[END_REF] and [START_REF] Arora | Generalization and equilibrium in generative adversarial nets (gans)[END_REF] expose the problem of distances as a more complex issue than what was previously thought. We mention this as a possible future research direction for improving unsupervised learning techniques. While [START_REF] Arora | Generalization and equilibrium in generative adversarial nets (gans)[END_REF] build a framework where the properties of the networks are implicitly carried through the notion of ℱ-distance, [START_REF] Arjovsky | To appear in ICML[END_REF] propose a connection with optimal transport where the properties of the solution are exposed more clearly via the concept of ground distance. This

is still an open problem that relates to the difficult issue of defining a similarity function between images, but we believe optimal transport and ground distances reflect an interesting abstraction to the problem of GANs.

Conclusion of this chapter

In this chapter, we described our work on the difficult subject of unsupervised learning, that underwent a surge in interest thanks to the recent advances in Generative Adversarial Networks (GANs).

In Section 5.2 we described the GAN algorithm proposed by Goodfellow et al.

[2014] along with its shortcomings and issues; this method corresponds to a problem that is not defined as clearly as the ones that were addressed in Chapters 3-4 .

Therefore, this part of our research is more exploratory, and we are seeking trails to improve our knowledge of unsupervised learning with the belief that this is important for solving visual recognition tasks that are currently out of reach.

First, in Section 5.3, we investigated the problem of evaluating the quality of a learnt GAN. We proposed a method based on classifier two-sample tests, that let us perform a first level of model selection by eliminating worst cases. In particular, during the course of these experiments, we observed that GAN discriminators are usually good enough to discriminate reliably between real samples and generated samples once training is stopped. One of our hypotheses to explain this result is artifacts corresponding to a signature of the generation process. In future work, we could study whether this issue still holds with newer GAN algorithms; such a signature can have consequences when addressing tasks such as domain adaptation, as e.g. proposed by [START_REF] Ganin | Domain-adversarial training of neural networks[END_REF], if data is to be processed by a neural network further down in the pipeline.

Second, in Section 5.4 we investigated links between generative adversarial networks and the concept of causality. Inspired by Lopez-Paz et al. [2017] demonstrating the existence of a causal signal in images, we designed a synthetic experiment with a physics simulator to build a dataset that we expect carries a causal component:

the plate of the marionette is the cause of the position of the body below which is the effect. While we weren't able to retrieve this causal structure using a GAN, we believe this task can be solved, and these experiments can be revisited with better training algorithms and possibly lead to better understanding of causal signals. Still, in order to illustrate the capabilities of GANs in the context of causality, we also proposed a two-sample test method to address the task of causal discovery on real data from the Tübingen cause-effect pairs dataset, with state-of-the-art results using ensembles, highlighting the promise of these methods for causal discovery.

Finally, in Section 5.5, we investigated different distances between distributions, that expose the following issue: we don't know what GANs are learning. Using recent insights from [START_REF] Arora | Generalization and equilibrium in generative adversarial nets (gans)[END_REF] and [START_REF] Arjovsky | To appear in ICML[END_REF], we get better understanding of the depth of this problem. What is learned is likely to depend on the architectures that are involved, and one interpretation (based on the idea of the neural net distance of [START_REF] Arora | Generalization and equilibrium in generative adversarial nets (gans)[END_REF]) is that generators attempt to match the data distribution up to the invariances carried by the discriminator and its convolutional neural network nature; however the dynamics of this learning process are still

unknown. An alternative point of view described by [START_REF] Arjovsky | To appear in ICML[END_REF] proposes to see GANs in an optimal transport optimization framework, and provides a stable GAN training algorithm. Further study with our toy experiment let us use an optimal transport criterion in practice, and observe that the core problem consists of building an appropriate ground distance to define more clearly how the distributions 𝑝 𝑔 and 𝑝 𝑑𝑎𝑡𝑎 are matched; this relates to the difficult issue of building a similarity function between images. In future work following this trail, we want to study what properties should be necessary in such metrics with the goal of building one that would allow extracting knowledge from unsupervised data.

Chapter 6

Discussion

In this chapter we review the contributions of this thesis, and discuss possible directions for future research.

Contributions of the thesis

Chapter 3 -Learning and Transferring Mid-Level Image Representations using Convolutional Neural Networks describes our first contribution to the field. We proposed a pre-training method that allows generalizing the performance improvements obtained by [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] using the large ImageNet database, to smaller-scale tasks that are more common in computer vision, notably the popular Pascal VOC classification benchmark [START_REF] Everingham | The pascal visual object classes (VOC) challenge[END_REF]) where our method outperformed the state of the art at the time of publication. Our method consists of training a CNN on a large source dataset where the amount of data alleviates the overfitting issues, then use a subset of the learned network to initialize another one designed for a target task, where the amount of data is smaller.

In Chapter 4 -Is object localization for free? Weakly-supervised learning with convolutional neural networks, we improved the method described in Chapter 3 by decreasing the amount of supervision necessary for performing the classification task. In particular, we observed that for a classification task, a neural network activates where relevant patterns are present, exposing the statistical learning nature of these methods; we built on this mechanism to predict the location of objects in images while only knowing at training time that they are present or absent, thus achieving a form of weak supervision in an end-to-end setup, also outperforming the state of the art at the time of publication for image classification on the Pascal VOC benchmark. This procedure relies on the fact that discriminative parts for classification are usually located on objects, although we show that the context may be sufficient for taking a decision sometimes because of the correlations in datasets: recognizing a kitchen is often enough to say that a fork and knife are present in the image.

In Chapter 5 -Unsupervised learning with CNNs -we followed the direction of less supervision and investigated unsupervised learning. The current successful methods in computer vision build on data and supervision to solve tasks, but providing enough annotated data to train an algorithm can be too costly and we look for alternatives. The field of unsupervised learning corresponds to a different challenge in the sense that there are no clear criteria or benchmarks for measuring progress.

Therefore this research is much more exploratory, and we are seeking ways to correctly frame the problem of extracting knowledge from unlabeled data.

We studied the recent trend of Generative Adversarial Networks proposed in Goodfellow et al. [2014], that allow generating samples resembling a reference real dataset, and focused first on the issue of evaluating this procedure. We explored the usage of classifier-based statistical two-sample tests, and noticed in our experiments that such an approach, performing binary classification between real data and generated data, is likely to fail due to artifacts resulting from the constraints applied to the generator function, but that this issue can be alleviated by performing a CNN feature transform prior to the procedure, in order to rely only on "natural image" statistics. This allows us to perform a first level of model selection when training a set of GANs.

Then, building on the fact that causal links happen naturally in the real world, and work by Lopez-Paz et al. [2017] showing that these can be observed in the form of a statistical footprint in images, we proposed a synthetic experiment inspired by mar-ionettes carrying a causal structure to illustrate this idea, and we proposed a method based on GANs and two-sample tests for performing causal discovery, ie. given a sample of data points (𝑥 𝑖 , 𝑦 𝑖 ), determining whether 𝑋 causes 𝑌 or 𝑌 causes 𝑋 on the Tübingen cause-effect pairs dataset, with promising results. This method shows that a form of causal signal can be captured with neural network-based algorithms.

Finally, since Generative Adversarial Networks learn by minimizing a distance between generated and reference image distributionss, we focused on the subject of distances between distributions and conducted a toy experiment to understand the subtleties of different approaches such as the Kullback-Leibler and Jensen-Shannon divergences, with a focus on the Earth Mover Distance related to the new Wasserstein-GAN algorithm of [START_REF] Arjovsky | To appear in ICML[END_REF]. Because of the restriction imposed by the usage of fixed neural network architectures, as pointed in the formalization of [START_REF] Arora | Generalization and equilibrium in generative adversarial nets (gans)[END_REF], current algorithms minimize approximations to these distances, but the nature and the practical consequence of such approximations is not understood well.

Future work

Built-in invariances in CNNs. It is not clear what makes CNNs and their features so powerful. While we showed in Chapter 3 that using more annotated data results in higher performance, attempts were also made at pre-training networks from unsupervised data, as proposed by e.g. [START_REF] Doersch | Unsupervised visual representation learning by context prediction[END_REF], [START_REF] Wang | Unsupervised learning of visual representations using videos[END_REF] or [START_REF] Bojanowski | Unsupervised Learning by Predicting Noise[END_REF]. The high performance obtained in these works expose the role of the bottom-up architecture, and suggests that a well-initialized CNN provides already good feature descriptors for visual recognition. Therefore, it is possible that the performance is the result of (i) being able to train a network, initializing its parameters correctly, and (ii) having similar data in the source and target datasets thus making the network more sensitive to relevant common patterns. One further research direction would be to understand the balance between the importance of data and the invariances built in the architecture in designing high-performing descriptors. The scattering networks line of research, led by [START_REF] Bruna | Invariant scattering convolution networks[END_REF],

notably explores this direction to understand what are these invariances.

Causality. Unsupervised learning is a field of many open questions, and so far, the main one is "how to do it?", in contrast with supervised learning, where we are interested in "how to do it better?". For this reason, perspectives are wide open but still our work aims at proposing potential directions for future research. In this context, we believe that understanding the concepts of causality is important, as causal links express themselves naturally in nature, and harnessing these in an unsupervised manner would provide additional signal to learn from and improve our algorithms. For example, capturing the physical causal structure of a marionette using only observations would be a great step towards understanding links between objects.

In this context, we showed that GANs were able to capture a causal signal in the particular setup of cause-effect discovery [START_REF] Mooij | Distinguishing cause from effect using observational data: methods and benchmarks[END_REF]); one next step would be to investigate ways to map noise following a causal structure with data also following a causal structure. The goal would be to control separately at generation time, by varying the appropriate components of the generator input, parts of the resulting image that correspond to causes, and parts that correspond to effects. Achieving this would give further insights on the causal relationships between objects in scenes, and may lead to better usage of unlabeled data. and what kind of distance between the real data and the generated data is being optimized. The observations of [START_REF] Theis | A note on the evaluation of generative models[END_REF] show that there is no universal metric for measuring a distance between probability distributions, exposing the depth of this problem. With the insightful works of [START_REF] Arora | Generalization and equilibrium in generative adversarial nets (gans)[END_REF], formalizing the distance problem better by introducing an architecture-dependant distance (the neural net distance), and [START_REF] Arjovsky | To appear in ICML[END_REF] introducing a theoretical connection to optimal transport optimization, we advocate the study of distance metrics between images In Section A.2, we will describe the problem of classification, and show in particular that many tasks in computer vision can be formulated as a classification task.

In Section A.3, we get interested in the mathematical interpretation of classification, as an optimization problem where the goal is to minimize what is called the empirical risk, that describes the performance of a classifier function for a task and dataset.

In Section A.4, we will introduce continuous loss functions that approximate the empirical risk in a differentiable way, allowing the use of gradient descent methods.

Gradient descent methods allow using parameterized differentiable functions as classifiers; neural networks fit in this class as we will see in Appendix B.

In Section A.5 we will mention convergence theorems for gradient descent algorithms, and also introduce stochastic gradient descent, which is the standard algorithm for training neural networks.

A.1 Data

We would like to teach computers how to do reasoning. Many approaches are also being explored, such as unsupervised learning that we investigate in Chapter 5, or reinforcement learning, which consists of training an algorithm to perform the best actions in an environment to maximize a reward.

The approach that we describe in this Appendix, supervised learning, consists of providing examples along with our understanding of the examples, and training an algorithm to mimic human reasoning.

A.1.1 Supervised learning with datasets

Let 𝒳 be a set containing observations, where 𝑥 𝑖 live. We call this the input space.

Let 𝒴 be the set of possible labels for a sample 𝑥 𝑖 ∈ 𝑋. We call this the label space. Providing labels for inputs is called supervision. Each 𝑦 𝑖 ∈ 𝑌 is a ground truth label. In the dataset paradigm, a machine learns by observing examples that are provided by the user, following a distribution 𝑝(𝑥, 𝑦). Sampling these observation defines the chosen granularity of the predictions and thus the level of invariance that we want the machine to learn.

• Collecting the labels 𝑦 by asking human experts: while in our case, we expect human agreement on deciding whether an image is of a dog or of a cat, the consistency of labeling is not always verified. In the case of more subjective label spaces (e.g. {beautiful, not beautiful}), 𝑝(𝑦|𝑥) carries information related to the human collection process.

Building general learning systems is very difficult because of these issues, and it was pointed out in [START_REF] Torralba | Unbiased look at dataset bias[END_REF] that for a given recognition task, performance was not consistent across datasets when tested. This means that the behavior of a learning system depends on the dataset that was used for training. In supervised learning, a machine will only learn from given data; no more, no less. For example, if a poorly-balanced dataset contains 95% of samples corresponding to a same label, an easy solution for a learning algorithm will be to output that label and ignore the input, yielding 95% accuracy but not useful in practice.

A.1.3 Training set, validation set, testing set

Datasets are usually split in three subsets:

• the training set, which is used for learning,

• the validation set, which is kept aside and used to check the performance on unknown examples and/or optimize hyperparameters such as the architecture of the classifier,

• the testing set, to allow final comparison with other research teams.

Good practice in machine learning requires the testing set to be completely unknown to the user building a learning setup. In the best case, this testing set is used only once for the final evaluation, for comparison to other setups by an external software: the correct labels are unknown to the user.

If the classification setup has any kind of hyper-parameters (such as "what kind of learning algorithm should we use?"), a subset of the training set is kept on the side along with the corresponding labels: we call it the validation set. This validation set will be used to tune the hyper-parameters for the best performance, hoping that it will lead to the best performance on the testing set. Tuning consists exactly of trying different values until finding the one that works best.

Conclusion

We have discussed that learning based on data can be subject to various biases due to data collection and human decisions. A trained algorithm is meant to be run ultimately "in the wild", and when building a setup the goal is to reproduce these conditions as precisely as possible. This goal can only be reached up to some point, depending on the knowledge and the effort of the practitioner. We use datasets to define the empirical risk in Section A.3.

A.2 Classification

We now dive deeper in learning, and study the important case of classification, which is the basic building block of visual recognition systems. Classification is a specific learning task, where the label space 𝒴 is discrete and finite. In this case, each element of 𝒴 is called a class, and we want to infer which class corresponds to a given sample 𝑥 ∈ 𝒳 . For each 𝑥, there is one and only one corresponding label 𝑦 ∈ 𝒴. We want to build a classifier 𝑓 ∈ ℱ = 𝒳 → 𝒴 such that ŷ = 𝑓 (𝑥) = 𝑦 for all (𝑥, 𝑦) ∼ 𝑝(𝑥, 𝑦).

Different classification tasks have different performance metrics. We mention three examples below.

A.2.1 Different variants of classification

Binary classification. In binary classification, the goal is to build a function 𝑓 that will be able to answer a binary question given a data sample 𝑥, providing a prediction ŷ ∈ 𝒴 = {𝑦𝑒𝑠, 𝑛𝑜}. ŷ = 𝑓 (𝑥) ∈ {𝑦𝑒𝑠, 𝑛𝑜} answers "is there a cat on this image?".

We would like 𝑓 to provide the correct prediction on as many samples as possible. In this case, our performance metric is "how often does 𝑓 provide the correct prediction?". This is the most general case. In Section A.3 we will describe the 0-1 loss function that reflects the performance of 𝑓 for this metric.

Attribute / multi-label classification. One simple extension of this would be to have many independent predictions for a given input. ŷ1 = 𝑓 1 (𝑥) ∈ {𝑦𝑒𝑠, 𝑛𝑜} answers "is there fur?", ŷ2 = 𝑓 2 (𝑥) ∈ {𝑦𝑒𝑠, 𝑛𝑜} answers "are there paws?", ŷ3 = 𝑓 3 (𝑥) ∈ {𝑦𝑒𝑠, 𝑛𝑜} answers "is it a cute animal?".

In this case, our performance metric can be "how often do all 𝑓 𝑖 provide a correct prediction". This is a more refined case than the binary, and is useful when many questions are considered simultaneously.

Multi-class classification (forced-choice). One more specific extension is the forced-choice classification problem. In that case, there are multiple possible answers to the question, but we add the constraint that only one of them can be correct at a time.

ŷ = 𝑓 (𝑥) ∈ {𝑐𝑎𝑡, 𝑑𝑜𝑔, 𝑐𝑜𝑤, ℎ𝑜𝑟𝑠𝑒} .

In this case, our performance metric is "how often does 𝑓 provide the correct prediction among the possible choices". This is useful in problems such as digit recognition for example or ImageNet classification [START_REF] Russakovsky | ImageNet large scale visual recognition challenge[END_REF]), when we know in advance that the input is in a given finite set. Overfitting is a major issue in learning setups, and can be detected on a classifier by observing that its performance on the validation set is significantly below its performance on the training set. While it can be easily detected, it is not easily fought, and many machine learning techniques -e.g. regularization as discussed in A.4.2 -are meant to alleviate this problem.

A.3.2 Overfitting

A.3.3 Restricting to parameterized functions

As mentioned above, one trivial solution to the previous optimization problem is to build a function 𝑓 that knows the correct label 𝑦 𝑖 for all the inputs 𝑥 𝑖 in the dataset, and gives an arbitrary response everywhere else in the domain 𝒳 .

However we are interested in generalizing beyond the dataset: if two samples 𝑥 𝑎 and 𝑥 𝑏 are similar, then their corresponding labels 𝑦 𝑎 and 𝑦 𝑏 should be similar as well. In order to enforce a form of continuity on the predictions, there needs to be restrictions on the set of functions ℱ that we will consider.

The general set of functions ℱ = 𝑋 → 𝑌 is difficult to use because it is infinite.

In order to perform practical operations, we restrict ℱ to functions that can be completely defined by a set of continuous parameters 𝑤 ∈ R 𝑑 such that:

𝑓 𝑤 (𝑥) = 𝑓 (𝑥, 𝑤) = ŷ, (A.6)
with 𝑓 𝑤 ∈ ℱ. This makes the optimization problem more tractable because we are now looking for a finite set of weights 𝑤 * such that:

𝑤 * := argmin 𝑤∈R 𝑑
𝑅 𝑒𝑚𝑝 (𝑓 (., 𝑤)).

(A.7)

In general we want 𝑓 to be differentiable w.r.t. 𝑤; this will allow the use of gradient descent algorithms as described in Section A.4.

A.3.4 Capacity

The form of 𝑓 (., 𝑤) (how the parameters 𝑤 are used by the function) is a restriction that defines a subset of ℱ. For example we can require 𝑓 to be a perceptron or a convolutional neural network following a chosen architecture. Depending on the restrictions imposed on the set ℱ, classifiers are more or less prone to overfitting, depending on their ability to learn specific patterns in examples, which is called capacity and corresponds to the flexibility of a set of functions. The notion of capacity corresponds to an idea that is more precisely defined by measures such as the VCdimension described in [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF].

The capacity of a classifier can be easily adjusted by increasing or decreasing the number of parameters 𝑑 (dimensionality of 𝑤) that can be learned during training.

There is a careful balance to find when it comes to capacity. If it is too small, then the classifier will not be able to learn the redunduncies in the dataset: the predictions

A.4.2 Regularization

Regularization. However, in order to suffer less from overfitting, it can be helpful to add regularization terms to the surrogate loss function. As an example, one common regularization term is the 𝐿 2 penalty:

𝑅𝑒𝑔 𝐿 2 (𝑤) = ||𝑤|| 2 . (A.
12)

The optimization problem becomes: .13) This new term will add a penalty to solutions where the norm of 𝑤 is high. It means that the learning algorithm will be more likely to sacrifice some prediction performance on the training set in order to get smaller values for the parameters in 𝑤. How "likely" depends on the strength of the regularization, which is the value of 𝜆.

𝑤 * = argmin 𝑤∈R 𝑑 𝐶 𝑟𝑒𝑔𝑢𝑙𝑎𝑟𝑖𝑧𝑒𝑑 (𝑤) = argmin 𝑤∈R 𝑑 [𝐶(𝑤) + 𝜆𝑅𝑒𝑔 𝐿 2 (𝑤)] . (A
As a result, the function 𝑓 (., 𝑤) becomes smoother, reducing overfitting, and in some cases will generalize better to samples unseen by the learning algorithm. 𝜆 is a hyper-parameter that can be tuned for optimal generalization performance on the validation set.

Objective functions. The sum of the surrogate loss and the (possibly many) regularization terms is called an objective function, that we minimize using an optimization algorithm. However, and especially in the context of neural networks, many regularization procedures have no closed-form expression (such as Dropout, described in [START_REF] Srivastava | Dropout: a simple way to prevent neural networks from overfitting[END_REF]). In these cases, learning is done by minimizing an objective function that can not be explicitly computed.

We illustrate this procedure below, in

C ( w)

Figure A-6: Illustration of gradient descent. We show level sets of the convex function 𝐶(𝑤). We start with an initial parameter 𝑤 0 and iterate in the direction of steepest descent to progressively reach the minimizer 𝑤 * .

A.5.1 Gradient descent convergence

Theorem 1 (Gradient descent convergence). Let 𝐶 : R 𝑑 → R be convex and differentiable. Let ∇𝐶 be Lipschitz-continuous with constant 𝐾 > 0:

∀𝑢, 𝑣 ∈ R 𝑑 , ||∇𝐶(𝑢) -∇𝐶(𝑣)|| ≤ 𝐾||𝑢 -𝑣||.
(A.17)

Gradient descent with fixed step size 𝛾 < 1/𝐾 satisfies: .18) This means that gradient descent eventually converges given enough iterations.

𝐶(𝑤 𝑡 ) -𝐶(𝑤 * ) ≤ ||𝑤 0 -𝑤 * || 2 (2𝛾𝑡) . ( A
Theorem 2 (Gradient descent convergence with milder assumptions). This theorem introduces the notion of general convexity, as proposed in [START_REF] Bottou | Online algorithms and stochastic approximations[END_REF].

• the second moment of H has bounded growth: Extension to non-convex cases. [START_REF] Bottou | Online algorithms and stochastic approximations[END_REF] extends this theorem to prove almost-sure convergence to extremal points by showing that the magnitude of the gradient converges to zero. This implies convergence to extremal points, as shown in This form of convergence implies that given an random initial set of parameters 𝑤 0 , there is no guarantee that optimization will lead to a satisfying solution.

∀𝑤 ∈ R 𝑑 ,
Neural networks are particularly affected by these issues, as SGD is the core algorithm for training them given the high cost of gradient computation, as we will see in Appendix B. As a consequence, producing and reproducing results is difficult, and much time is usually spent tuning the hyperparameters for training to succeed.

Conclusion

We show convergence theorems for gradient-based methods, describe stochastic gradient descent, and mention the underlying limitations in the non-convex cases that include neural networks, in particular the convergence towards extremal points that, given a random initial point, can make the production and reproduction of results difficult.

A.6 Conclusion

In this Appendix, we provided a short introduction to supervised classification and its basics. In Section A.1, we described the data that we can use, and showed that in supervised learning, the knowledge present in a dataset is an illustration of the procedure that was used to collect it. This is a core limitation of supervised learning, as in this scenario a machine can only learn concepts that are simple enough for humans to annotate and agree upon.

In Section A.2, we described the problem of classification, and showed that many tasks in computer vision can be engineered into one (or many) classification task(s).

This special case of machine learning allows for many applications.

In Section A.3, we described the mathematical interpretation of classification as an optimization problem over parameterized functions, where the goal is to minimize what is called the empirical risk, which describes the performance of an algorithm on a training set. We mentioned one of the major issues in machine learning, overfitting, where a function learns to minimize this empirical risk, but not in a way that allows algebra operations that are involved in this layer, explaining the great success of GPUs for computation in this context.

In Section B.6 we will provide more insights on the practical usage of these algorithms; we will also mention problems related to random initialization of weights and learning rates along with recent methods for alleviating these issues. We will also mention briefly the case of recurrent neural networks.

B.1 Math preliminaries

Many of the computations in a neural network are based on dot-products. In this section, after introducing some notation on derivatives, we will briefly discuss this operation. We will in particular see that a set of dot-products can be seen as a matrix operation; this will be very important for implementation purposes because computers perform linear algebra very efficiently.

B.1.1 Partial derivative notation

Neural network training relies heavily on gradient descent, therefore this appendix chapter involves partial derivatives. The representation of data is usually done with tensors -multi-dimensional arrays for which matrices are a special case of dimension 2, and we need to extend the chain rule of derivatives to tensors.

Let 𝑑 𝑥 1 , 𝑑 𝑥 2 , 𝑑 𝑥 3 , 𝑑 𝑦 1 , 𝑑 𝑦 2 , 𝑑 𝑦 3 be positive integers. Given tensors 𝑋 ∈ R 𝑑 𝑥 1 ×𝑑 𝑥 2 ×𝑑 𝑥 3 , 𝑌 ∈ R 𝑑 𝑦 1 ×𝑑 𝑦 2 ×𝑑 𝑦
3 , and a scalar 𝐿 ∈ R, we will use the partial derivative notation to extend Jacobian matrices to tensors, such that:

• 𝜕𝐿 𝜕𝑋 is a gradient tensor 𝐺 ∈ R 𝑑 𝑥 1 ×𝑑 𝑥 2 ×𝑑 𝑥
3 with the following entrywise definition:

∀𝑖, 𝑗, 𝑘 𝑔 𝑖𝑗𝑘 = 𝜕𝐿 𝜕𝑥 𝑖𝑗𝑘 (B.1) • 𝜕𝑌 𝜕𝑋 ∈ R 𝑑 𝑦 1 ×𝑑 𝑦 2 ×𝑑 𝑦 3 ×𝑑 𝑥 1 ×𝑑 𝑥 2 ×𝑑 𝑥
3 is a "Jacobian" tensor 𝑇 with the following entrywise definition:

∀𝑝, 𝑞, 𝑟, 𝑖, 𝑗, 𝑘, 𝑡 𝑝𝑞𝑟𝑖𝑗𝑘 = 𝜕𝑦 𝑝𝑞𝑟 𝜕𝑥 𝑖𝑗𝑘 (B.2)

• the chain rule holds using an appropriate tensor reduction:

𝜕𝐿 𝜕𝑋 = 𝜕𝐿 𝜕𝑌 𝜕𝑌 𝜕𝑋 (B.3)

B.1.2 The dot-product

The dot-product is an operation in Euclidean spaces that plays a crucial role in neural networks. A large portion of the mathematical operations in neural networks (especially in the convolution layer ) are more or less complicated combinations of dot-products. We take a look at how it works. If the angle is large, directions are roughly opposite, 𝑐𝑜𝑠(𝜃) < 0 and 𝑌 < 0.

If the angle is small, the directions are similar, 𝑐𝑜𝑠(𝜃) > 0 and 𝑌 > 0.

Algebraic view. The equivalent algebraic view involves the coordinates of the vectors, which is much more convenient for implementation and differentiation. Let Computing dot-products between many vectors (𝑎 𝑖 ) 𝑖 and many vectors (𝑏 𝑗 ) 𝑗 can be seen as a matrix multiplication operation for which there are extremely optimized algorithms available, e.g. OpenBLAS (http://www.openblas.net) on CPU or cuBLAS (https://developer.nvidia.com/cublas) on nVidia GPUs, often close to the limits of the hardware.

B.2 Neural network architectures

We saw in Appendix A that the classification problem can be addressed using parameterized differentiable functions 𝑓 (𝑥, 𝑤) (with input 𝑥 and parameters 𝑤) and optimizing a cost functional 𝐶(𝑤) with gradient descent. Given a loss function 𝐿 and a dataset 𝒟 = {𝑥 𝑖 , 𝑦 𝑖 } 1≤𝑖≤𝑁 , we want to solve the following optimization problem, as defined in Section A.4,Equation (A.11):

𝑤 * = argmin 𝑤∈R 𝑑 𝐶(𝑤) = argmin 𝑤∈R 𝑑 𝑁 ∑ 𝑖=1 𝐿(𝑓 (𝑥 𝑖 , 𝑤), 𝑦 𝑖 ). (B.8)
As we will use Stochastic Gradient Descent for this problem, (see Section A.5), we will need to compute 𝜕𝐿 𝜕𝑤 . Our goal in this section is to review the properties that are required to build suitable functions following a modular graph-based architecture, and more importantly, how to compute their gradient.

Notations. In this section, we will consider many layers, and therefore use superscripts to refer to the layer index. For a layer indexed with 𝑖, 𝑓 𝑖 is the layer function,

𝑥 𝑖 is the input, 𝑤 𝑖 is the set of parameters, and 𝑦 𝑖 is the output. When no superscript is used, we consider the whole network.

B.2.1 Graph-based architectures

Neural networks are differentiable parameterized functions 𝑓 = (𝑥, 𝑤) ↦ → ŷ ∈ ℱ = 𝒳 × 𝒲 → 𝒴 defined by a directed acyclic graph (DAG) of nodes called layers going from the data input 𝑥 ∈ 𝒳 to the prediction output ŷ ∈ 𝒴, with a set of parameters 𝑤. In other words:

• We need to use differentiable and parameterized functions in order to use gradient descent algorithms to train them by optimizing their parameters, as explained in Section A.3. We have ŷ = 𝑓 (𝑥, 𝑤).

• We build suitable functions by composing smaller functions following a DAG.

This allows the use of the backpropagation algorithm [START_REF] Rumelhart | Learning representations by back-propagating errors[END_REF])

to compute gradients, that we will describe in B.2.2.

• Layers implement these smaller functions, and are the base nodes of this DAG.

They can be of different types, as we will show in examples in Sections B.3-B.4-B.5. Each layer indexed by 𝑖 ≤ 𝑛 𝑙𝑎𝑦𝑒𝑟𝑠 has a set of parameters 𝑤 𝑖 such that 𝑤 ∈ R 𝑑 contains the elements of all the sets 𝑤 𝑖 . 𝑤 𝑖 can be empty, which means layer 𝑖 has no parameters.

We will first describe layered architectures, that are used to define neural networks, and explain the properties that are necessary in layers for implementing backpropagation in a directed acyclic graph.

Example of neural network architecture. We start with an example shown in ŷ = 𝑓 (𝑥, 𝑤) = 𝑓 4 (𝑓 3𝑎 (𝑓 2 (𝑓 1 (𝑥, 𝑤 1 ), 𝑤 2 ), 𝑤 3𝑎 ), 𝑓 3𝑏 (𝑓 2 (𝑓 1 (𝑥, 𝑤 1 ), 𝑤 2 ), 𝑤 3𝑏 ), 𝑤 4 ), (B.9) which is quite difficult to read. While this shows that the network effectively corresponds to a mathematical composition of functions, observing the graphs is much easier.

B.2.2 Backpropagation

The backpropagation algorithm is simply a generalization of the chain rule for composed functions. It allows computing the gradient of a function with respect to each element in a DAG that defines the function. Layers are the building block elements of neural networks that will be laid out on a DAG. Each layer 𝑖 contains a function 𝑓 𝑖 and a set of learnable parameters 𝑤 𝑖 called weights, which can be the empty set. The goal is to compute the gradient 𝜕𝐿 𝜕𝑤 𝑖 for all the layers in the graph, in order to obtain • compute its output 𝑦 𝑖 = 𝑓 𝑖 (𝑥 𝑖 , 𝑤 𝑖 ),

ŷ x f 1 f 2 f 3a f 3b
• propagate the loss gradient to its input: compute 𝜕𝐿 𝜕𝑥 𝑖 , given 𝜕𝐿 𝜕𝑓 𝑖 . This is the chain rule for composed functions:

𝜕𝐿 𝜕𝑥 𝑖 = 𝜕𝐿 𝜕𝑓 𝑖 𝜕𝑓 𝑖 𝜕𝑥 𝑖 , (B.10)
• propagate the loss gradient to its weights: compute 𝜕𝐿 𝜕𝑤 𝑖 , given 𝜕𝐿 𝜕𝑓 𝑖 . This is the chain rule for composed functions:

𝜕𝐿 𝜕𝑤 𝑖 = 𝜕𝐿 𝜕𝑓 𝑖 𝜕𝑓 𝑖 𝜕𝑤 𝑖 . (B.11)
Directed and Acyclic. A directed acyclic graph ensures that the network can be traversed in order, such that when we want to evaluate a layer, we know its inputs are available. We show a topologically sorted version of our example architecture in Figure B-6. Similarly, when evaluating gradients for a layer, we know that the gradient of the loss with respect to the outputs is available.

Layer function f i

Parameters w i

Output y i =f i (x i ,w i ) 𝜕𝑓 𝑖 𝜕𝑤 𝑖 and 𝜕𝑓 𝑖 𝜕𝑥 𝑖 can be used in the chain rule because the function 𝑓 𝑖 is known. When the graph is directed and acyclic, it can be traversed in order, which allows forward (going right) and backward propagation (going left). Topological sorting ensures that all the outputs of the parents are available to their children when they are evaluated. Each individual layer needs to be able to execute the three following functions for the procedure to succeed:

Input x i =y i-1 y i =f i (x i ,w i ) w i x i
ŷ x f 1 f 2 f 3a f 3b f 4 L
ŷ x f 1 f 2 f 3 a f 3 b f 4 Loss L f 1 f 2 f 3a f 3b
• Compute its output given an input: 𝑦 𝑖 = 𝑓 𝑖 (𝑤 𝑖 , 𝑥 𝑖 ).

• Compute the gradient with respect to its input, given the gradient with respect to its output:

𝜕𝐿 𝜕𝑥 𝑖 = 𝜕𝐿 𝜕𝑓 𝑖 𝜕𝑓 𝑖 𝜕𝑥 𝑖 .
• Compute the gradient with respect to its parameters if any, given the gradient with respect to its output:

𝜕𝐿 𝜕𝑤 𝑖 = 𝜕𝐿 𝜕𝑓 𝑖 𝜕𝑓 𝑖 𝜕𝑤 𝑖 .
These are the only requirements, and they allow building setups with arbitrarily complex architectures. With the gradient available, the neural network can be trained to optimize the objective using gradient descent methods. In Sections B.3-B.4-B.5 we will introduce example layers that have all the required properties, and can be used as building blocks for designing neural networks.

Jacobians. In this section, the partial derivatives 𝜕𝑓 𝑖 𝜕𝑥 𝑖 and 𝜕𝑓 𝑖 𝜕𝑤 𝑖 are in fact Jacobian matrices. In some cases, such as the matrix-vector multiply (𝑌 = 𝑊 𝑋, see below), the Jacobian matrix (here, 𝑊 𝑇 ) is easy to obtain in closed form. But in more complicated cases, this Jacobian is only useful for theory; in practice 𝜕𝐿 𝜕𝑥 𝑖 and 𝜕𝐿 𝜕𝑤 𝑖 are computed directly from the gradient 𝜕𝐿 𝜕𝑦 𝑖 without using Jacobians.

B.3 Simple layers

We now describe some important layers that are used in neural networks, as well as their gradient computation.

Notations. In this section we consider only a single layer at a time, and subscripts will only be used to index elements in vectors. A vector 𝑋 ∈ R 𝑝 is described by a sequence of elements (𝑥 𝑖 ) 1≤𝑖≤𝑝 .

B.3.1 Fully-connected layer

This layer takes a vector 𝑋 ∈ R 𝑝 and outputs a vector 𝑌 ∈ R 𝑛 such that:

𝑌 = 𝑊 𝑋 + 𝐵 (B.12)
where 𝑊 ∈ R 𝑛×𝑝 (the weight matrix) and 𝐵 ∈ R 𝑛 (the bias matrix) are the parameters for this layer1 . The gradient can be propagated as follows:

𝜕𝐿 𝜕𝑋 = 𝑊 𝑇 𝜕𝐿 𝜕𝑌 (B.13) 𝜕𝐿 𝜕𝑊 = 𝜕𝐿 𝜕𝑌 𝑋 𝑇 (B.14) 𝜕𝐿 𝜕𝐵 = 𝜕𝐿 𝜕𝑌 (B.15)
This layer has (𝑝 + 1)𝑛 parameters in total. This number of parameters is defined when defining the layer (and the size of the matrix 𝑊 ). The input to this layer can be a flattened tensor, which is the same tensor but viewed as a vector with the same number of elements.

We illustrate the operations in

B.3.2 Elementwise nonlinearity

This layer takes a vector 𝑋 ∈ R 𝑝 and outputs a vector of same dimensionality 𝑌 ∈ R 𝑝 , by processing each coordinate independently with a non-linear function 𝜎 : R → R such that:

∀𝑖 ∈ [1, 𝑝] , 𝑦 𝑖 = 𝜎(𝑥 𝑖 ) (B.16)
The gradient can be propagated as follows:

∀𝑖 ∈ [1, 𝑝] , 𝜕𝐿 𝜕𝑥 𝑖 = 𝜕𝐿 𝜕𝑦 𝑖 𝜕𝜎 𝜕𝑥 𝑖 (B.17)
where 𝜕𝜎 𝜕𝑥 𝑖 corresponds to the slope of the function 𝜎 at 𝑥 𝑖 . This layer has no weights.

In common network architectures, many nonlinearity layers are present systematically after each weighted layer except for the last one. During backpropagation, the gradient values are multiplied by the slope, which can be small especially in the case of saturating functions. With many nonlinearities, this can have a multiplicative effect: the gradient magnitude can become very small, making optimization difficult. This is known as the vanishing gradient problem.

Popular non-linear functions (also called activation functions) include the Rectified Linear Unit (ReLU), Hyperbolic tangent (tanh) and Sigmoid; we show plots in Figure B-9. Nonlinearities are the main reason why neural networks are not convex functions2 ; for example, a sequence of two fully-connected layers is an affine transform, which is a convex function. But a nonlinearity between these layers makes it a non-convex function, giving it higher capacity and flexibility, and higher potential for classification purposes.

B.3.3 Softmax.

The softmax function is a particular non-linear function that transforms an input such that the coordinates are positive and sum to one; the transformed vector can then be interpreted as a probability distribution. It is the function 𝜓 such that 𝑌 = 𝜓(𝑋)

with:

∀𝑖 ∈ [1, 𝑝] , 𝑦 𝑖 = exp(𝑥 𝑖 ) ∑ 𝑝 𝑗=1 exp(𝑥 𝑗 ) . (B.18)
This function builds a probability distribution such that higher values of the input are exponentially preferred. This can be used in particular as a final layer for multi-class forced-choice classification, as done by [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] (see Section B.6). ReLU is non-saturating and allows propagating gradient easily at the cost of unbounded activation. Sigmoid and Tanh can make gradient vanish if the activation is in the flat gradient regime.

B.4 Tensor layers

In convolutional neural networks, in order to preserve the spatial information present in images, data is often represented as a tensor. Tensors are a generalization of matrices. One can see matrices as a special case of tensors, where the tensor rank is 2 (rows, columns).

Notations. In this section we consider only a single layer at a time, and subscripts will only be used to index elements in tensors. A three-dimensional tensor 𝑋 has an element 𝑥 𝑖𝑗𝑘 .

B.4.1 Feature maps

We start with the example of RGB (Red, Green, Blue) color images. Convolution layers generalize this by representing data over more feature maps according to patterns called convolution filters; we will describe this after the pooling layers below.

B.4.2 Pooling layers

Pooling layers, such as the max-pooling or the average-pooling, are special types of layers that are applied, in the case of images, to each feature map separately. They consist of aggregating neighboring elements in order to obtain an output of smaller height and width.

The sizes of the output map, ℎ 𝑜𝑢𝑡 and 𝑤 𝑜𝑢𝑡 , depend on the definition of the grid, usually smaller than those of the input ℎ 𝑖𝑛 and 𝑤 𝑖𝑛 . Pooling performs subsampling. We call the sizes of the tensor width, height, and depth as shown. Feature maps are concatenated over the depth dimension. Indexing of tensor elements is done such that for 𝑥 𝑎𝑏𝑐 , 𝑎 corresponds to the depth dimension, 𝑏 to the height dimension, 𝑐 to the width dimension.

We illustrate this procedure in Figure B-11.

Defining a grid with sizes and strides. In order to pool, one needs to define the arrangement of the pooling cells 𝐶(𝑖, 𝑗) indexed by their position in the grid: these define the neighborhood structure of the pooling operation.

The pooling size defines the size of the cell, and the pooling stride defines the distance between two consecutive cells. The pooling function. The pooling function is then applied to each of the cells defined by the size and stride. Popular pooling functions include:

• max, returning the maximum element of the cell.

• average, returning the average value of the cell.

• 𝐿 𝑝 -norm, returning the 𝐿 𝑝 norm of the cell. Max-pooling case. While the average and the 𝐿 𝑝 -norm functions are immediately differentiable, this is not the case for the max function. For the max-pooling operation, computing the gradient is done in the following way:

• As a result of the forward operation, we have 𝑦 𝑖𝑗 = 𝑥 𝑘 * 𝑚 * , where 𝑘 * , 𝑚 * are the coordinates of the maximal element.

• Within the corresponding cell, we set 𝑑𝐿 𝑑𝑥 𝑘𝑚 = 𝑑𝐿 𝑑𝑦 𝑖𝑗 if (𝑘, 𝑚) = (𝑘 * , 𝑚 * ), and 0 otherwise.

This means that the gradient is backpropagated through the maximal element of each Usually, the input is padded with zero elements (explicitly or implicitly) in order to avoid this case.

In the case of an overlapping grid, it is possible that an element backpropagates gradients from many cells. In this case, the gradient corresponding to an element corresponds to the sum of the gradient contributions of the cells in which it is involved.

Grid-summing is illustrated in the example of Figure B-15 (see blue and red cells).

If within a cell, two elements have the maximum value, then choosing which element (𝑘 * , 𝑚 * ) backpropagates the gradient is also an implementation choice. However, this collision case does not happen often with floating-point numbers in practice as those Bottom: gradient backpropagation. We compute the gradient corresponding to each cell. In the max-pooling case we copy the value of the output gradient 𝜕𝐿 𝜕𝑌 to the position of the largest element within each cell, then sum them according to the grid to obtain the input gradient 𝜕𝐿 𝜕𝑋 .

The red and blue cells overlap, propagating a value of 7 = 3 + 4 in the first row. The convolution operation consists of sliding a filter tensor of same depth dimensionality over the width and height dimensions, applying dot-products on each cell (sometimes with a stride between consecutive cells). We will describe it next. In this very simple case, the input is an 3-channel RGB image, and we can observe that the output maps react to edges of different orientations. In the upper layers of a network, however, it is more complicated to obtain an interpretable visualization, as the number of channels does not allow it.

However, [START_REF] Matthew | Visualizing and understanding convolutional networks[END_REF] provide a visualization in Figure B-24, that we will discuss in Section B.6. Tensor dot-product. We first define the dot-product between two tensors of same size U and V ∈ R 𝑎×𝑏×𝑐 , similarly to a vector dot-product:

(𝑈 |𝑉 ) = ∑ 𝑖,𝑗,𝑘 𝑢 𝑖𝑗𝑘 𝑣 𝑖𝑗𝑘 (B.19)
B.5.2 Single kernel forward computation.

We first start with the single-kernel case, where the convolution layer applies a single kernel to its input.

In the convolution layer, the input 𝑋 is a tensor of size 𝑛 𝑓 𝑒𝑎𝑡𝑢𝑟𝑒𝑠 × ℎ 𝑖𝑛 × 𝑤 𝑖𝑛 . A (square) weighted convolution kernel 𝑊 is a tensor of size 𝑛 𝑓 𝑒𝑎𝑡𝑢𝑟𝑒𝑠 × 𝑘 × 𝑘. We show the convolution of a single kernel 𝑊 with an input 𝑋 in Figure B-18.

First, the input 𝑋 is cut into a grid over the spatial dimensions (height and width), such that each cell tensor 𝐶 matches the size of the kernel tensor 𝑊 . We index 𝐶(𝑖, 𝑗) by its spatial position (𝑖, 𝑗) in the grid.

Then, each cell 𝐶(𝑖, 𝑗) is used in a dot-product with 𝑊 to obtain the value 𝑦 𝑖𝑗 in the output feature map 𝑌 . A bias value 𝑏, shared across the feature map for this kernel, is then added to all elements. This gives:

∀𝑖, 𝑗, 𝑦 𝑖𝑗 = (𝑊 |𝐶(𝑖, 𝑗)) + 𝑏 (B.20)
Remarks. We note that the output height ℎ 𝑜𝑢𝑡 and width 𝑤 𝑜𝑢𝑡 are smaller than those of the input as a consequence of the cell grid definition. When necessary, this issue can be addressed by padding the input tensor with enough zeros.

As a result of the convolution operation, the input is processed locally: each cell corresponds only to a small spatial portion of the input. In contrast, fullyconnected layers process their input globally, as they have no notion of sparsity or spatial distance.

The convolution operations usually account for the large majority of floatingpoint operations in a neural network (as we will see in B.6.2), therefore optimizing their execution is a critical issue that was addressed using GPU implementations by [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], explaining part of their current success.

B.5.3 Single-kernel backpropagation to inputs.

B.5.5 Remarks

Extension to multiple kernels. When using multiple kernels (and their corresponding biases), each of them results in a single independent feature map, and the output becomes a three-dimensional tensor of size 𝑛 𝑘𝑒𝑟𝑛𝑒𝑙𝑠 ×ℎ 𝑜𝑢𝑡 ×𝑤 𝑜𝑢𝑡 . For backpropagation to the input, the contributions of individual kernels and their corresponding map are summed to compute the input gradient.

Number of parameters.

A convolution layer has 𝑛 𝑘𝑒𝑟𝑛𝑒𝑙𝑠 × 𝑛 𝑓 𝑒𝑎𝑡𝑢𝑟𝑒𝑠 × 𝑘 × 𝑘 free parameters in the kernels, and 𝑛 𝑘𝑒𝑟𝑛𝑒𝑙𝑠 parameters in the biases. The number of free parameters can therefore be adjusted by choosing the number of kernels and their size.

Implementation. A convolution with a single kernel consists of dot-products between a kernel and many cells. This can be seen as a matrix-vector multiply operation.

In practice, a convolution layer consists of multiple kernels against many cells, which corresponds to a matrix-matrix multiply operation. We illustrate this in Figure B-21.

This linear algebra operation (Single-precision General Matrix Multiply -SGEMM) is extremely optimized in computers thanks to the BLAS formalism (Lawson et al.

[1979]), and can be computed by decomposing the output matrix in blocks and parallelizing computations. GPUs are designed for parallel processing, and allow running the convolution layer much quicker than on CPUs, granting the processing power necessary for convolutional neural networks research. Similar optimizations can be obtained for the backward operations. In particular the gradient computations can also be cast as convolution operations.

Overall, convolutional neural networks greatly benefit from the capabilities of GPUs for linear algebra.

Mini-batch parallelization. Using minibatches consists of executing the forward and backward operations in parallel across 𝐵 examples. This increases the total number of cells that are processed in the matrix multiplication described in Figure Arranging the cells into a matrix (of size (𝑛 𝑐𝑒𝑙𝑙𝑠 × cell dimensionality)), and the kernels into another matrix (of size (𝑛 𝑘𝑒𝑟𝑛𝑒𝑙𝑠 × cell dimensionality)) allows using efficient generic linear algebra routines such as the matrix multiplication. The result of this matrix multiplication is then rearranged into a tensor, exposing concatenated feature maps.

B-21. As a result, we obtain:

• a matrix multiply operation with larger matrices; SGEMM performance is closer to the hardware limits if matrices are large. More generally, parallelization is more efficient when the problem is large and made of independent subproblems (e.g. different images).

• A better estimate of the weight and bias gradient for the stochastic gradient descent learning, as it is averaged across samples.

B.6 In practice

B.6.1 Summary so far

Layered architectures We showed in Section B.2 that neural networks are arrangements of layers with specific properties within a directed acyclic graph, that allow running the backpropagation algorithm to compute gradient. This makes these functions fit in the machine learning framework that we described in Appendix A.

Core layers. In Sections B.3-B.4-B.5 we defined the core layers of neural networks, in particular the convolution, pooling, nonlinearity and fully-connected layers. Many more layers and variants exist, but the ones presented here are present in almost all successful applications. In particular, we show that the convolution layer can be easily reduced to linear algebra operations given the numerous dot-products involved.

Moreover, with mini-batch processing, many samples can be treated in parallel, which translates to larger matrices at computation time. Given that GPUs are especially efficient at processing large matrices (matrix multiplication can be processed in parallel easily by dividing the problem into submatrices), this explains why their introduction in machine learning improved neural networks significantly.

B.6.2 A famous architecture

AlexNet. We will take a look at the very important AlexNet architecture, which was proposed by [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] for the ILSVRC-2012 competition, and caused the shift to neural network methods in computer vision as we described in Chapter 2. We show the architecture in We omit the regularization layers (local response normalization and dropout for clarity) and refer to [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] for more details. We can observe in this architecture, which corresponds to a standard network in computer vision, that convolution layers are stacked on top of each other. We explain the consequence next.

Growing receptive fields with convolution layers. Each value in a feature map depends on a subset of the initial input image that is processed by the network. This

B.6.3 Training a network

Most of the advice mentioned here comes from the work of LeCun et al. [1998b], as these algorithms have been studied for a long time in the 90s, but this knowledge was refined during the years.

The major issue when training a deep multi-layered network is that the signal can vanish. In the forward phase, if the weights in layers are small, then the magnitudes of the output values decrease; with many layers, this has a multiplicative effect, and the signal can vanish entirely. Conversely, if the weights are large, then the values grow fast, and this can lead to numerical instabilities with unbounded activations such as the ReLU.

In the backward phase, in the case of saturating nonlinearities, the gradient is multiplied by the slope: if nonlinearities are mostly saturated, then this gradient can become too small to allow learning. Therefore, a couple settings were proposed.

Weight initialization. LeCun et al. [1998b] propose that data should first be normalized. The mean values of variables should be close to zero, their variances should be about the same (in general, 1), and in the best case they should be decorrelated.

With normalized inputs, data can be treated as a random variable with known variance. In neural networks, weights are initialized randomly; in general by following a centered gaussian or uniform distribution with variance 𝜎 2 . This allows choosing the magnitudes of the weights (through 𝜎) and therefore controlling the variance of the output of the a layer. Given a normalized centered and scaled input, the weights for a given neuron (e.g. for a convolution, its kernel parameters) should be drawn from a centered distribution with 𝜎 = 𝑚 -1/2 where m is the dimensionality of the kernel (the number of input variables to the dot-product or fan-in), if the desired output variance is 1.

This rule was refined over the years, notably with the formula proposed by Glorot and [START_REF] Glorot | Understanding the difficulty of training deep feedforward neural networks[END_REF], known as the "Xavier" initialization, drawing weights from a uniform distribution with variance 2 𝑛 𝑖 + 𝑛 𝑖+1

where 𝑛 𝑖 corresponds to the number of input variables (fan-in) for layer 𝑖. This ensures that the variances of the forward and The effect of this layer on the optimization procedure is not perfectly understood yet, but some insights were provided in [START_REF] Lafond | Diagonal rescaling for neural networks[END_REF].

Learning rates. When running stochastic gradient descent for optimizing the values of the weights, picking a good learning rate can become an issue. This is pretty much an unsolved problem in the difficult non-convex case of neural networks (although this issue was studied in LeCun et al. [1998b]), and practice suggests that values should be tried and cross-validated.

One commonly used practice, used in [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], consists of setting a global learning rate (initially 10 -2 ) on all the weight parameters, then decreasing it by a factor of 10 every time the validation loss reaches a plateau. We show a sketch of typical loss curves in Figure B-25.

Momentum. An alternative update rule for SGD (described in A.5) that is frequently used (in particular by [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF]) is the momentum acceleration method of [START_REF] Boris | Some methods of speeding up the convergence of iteration methods[END_REF] (also known as heavy ball method ) or its variant by Nesterov ) is manually decreased by a factor 10 (pointed with arrows), until the procedure converges.

[1983]. Both versions enjoy improved convergence rates compared to the plain version of SGD that we will not detail here; [START_REF] Sutskever | On the importance of initialization and momentum in deep learning[END_REF] also report the importance of these methods for training in practice.

Let 𝐶(𝑤) be a functional that we seek to minimize. The update rule for the momentum method is:

𝑣 𝑡+1 = 𝜇𝑣 𝑡 -𝜖∇𝐶(𝑤 𝑡 ), (B.24) (B.25) where 𝜇 ∈ [0, 1] is the momentum coefficient and 𝜖 > 0 is the learning rate.

𝑤 𝑡+1 = 𝑤 𝑡 + 𝑣 𝑡+1 ,
The update rule for Nesterov's Accelerated Gradient method is:

𝑣 𝑡+1 = 𝜇𝑣 𝑡 -𝜖∇𝐶(𝑤 𝑡 + 𝜇𝑣 𝑡 ), (B.26) (B.27) where 𝜇 ∈ [0, 1] is the momentum coefficient and 𝜖 > 0 is the learning rate.

𝑤 𝑡+1 = 𝑤 𝑡 + 𝑣 𝑡+1 ,
The intuition, in both cases, is that the weights are updated according to an exponential average of previous weights updates accumulated in a momentum vector.

In the version of Polyak, the new gradient is computed before the momentum is applied, in contrast to Nesterov's method that computes it after.

Adaptive optimizers. For the issue of learning rates, adaptive learning-rate optimizers such as RMSprop [START_REF] Tieleman | Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude[END_REF]), AdaGrad (Duchi et al.

[2011a], used in Chapter 4) or Adam (Kingma and Ba [2015b], used in Chapter 5), were proposed to avoid setting learning rates manually. The general intuition behind these adaptive algorithms is to scale the step size by the inverse of a running average of the gradient magnitude: when the gradient is small the step sizes are larger, and vice-versa.

Again, the effect of these methods on the optimization procedure is not understood as well as SGD yet, but their ease of use have popularized their usage.

Data augmentation. A popular regularization method for reducing overfitting in neural networks is data augmentation: this consists of applying a label-preserving transformation to input samples in order to artificially increase the size of the dataset.

An exemple used notably in [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] is the crop/flip scheme, that extracts patches from an input image by cropping the borders and horizontally flipping them with probability 0.5. We illustrate this scheme in Figure B-26. An experiment in [START_REF] Zhang | Understanding deep learning requires rethinking generalization[END_REF] shows that without data augmentation, it is possible to train a CNN on the ImageNet dataset (1 million images) with random labels, showing the very high capacity of these algorithms for memorizing a training set, and hinting at the usefulness of the data augmentation scheme. with their Long-Short Term Memory variant (LSTM, [START_REF] Hochreiter | Long short-term memory[END_REF]) mentioned in Chapter 2. These networks are useful in these cases because they are able to process sequences as input, and provide sequences as output.

Recurrent Neural Networks contain a hidden state that is updated with each element of the input sequence, and this state is used to produce elements in the output following, for instance, equations of the form: But the training algorithm for these recurrent networks, known as backpropagation through time (BPTT, [START_REF] Rumelhart | Learning representations by back-propagating errors[END_REF]), consists of unrolling the network for a fixed number of iterations, in order to build a Directed Acyclic Graph and execute the usual backpropagation algorithm for feedforward networks, except the parameters 𝑤 ℎ and 𝑤 𝑜𝑢𝑡 are shared between unrolled nodes (this doesn't contradict the directed acyclic assumption); the gradient for the recurrent unit is the sum of the contributions of all nodes. We show a sketch of the same recurrent unit in Figure B-28 after unrolling it for 3 steps to give intuition on the procedure.

ℎ 0 =
Even though RNNs appear to be a particular case of the standard neural networks, the training techniques and corresponding issues are different: when unrolling for a large number of steps (hundreds or thousands), the vanishing and exploding gradient problems can be more difficult to deal with due to the multiplicative effects, but we leave these out of the scope of this text.

B.7 Summary and conclusion

Summary. In this Appendix B, we show that (convolutional) neural networks are a particular set of parameterized functions that fit in the machine learning framework described in Appendix A. In Section B.2 we described the properties of the architectures that define these functions, as layers laid on a directed acyclic graph, enabling the use of the backpropagation algorithm. We also showed which operations each layer needs to run, for the procedure to succeed.

In Sections B.3-B.4-B.5, we described a set of important layers that are present in most neural network architectures, in particular the convolution, pooling, fullyconnected and nonlinearity layers, as well as methods for computing the appropriate gradients in the backward operations. In particular, we show that the numerous dot-products involved in computations can be seen as linear algebra operations on matrices, for which efficient algorithms are available.

In Section B.6 we focused on practice, and presented the network of [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] and, the study of its convolution filters provided in [START_REF] Matthew | Visualizing and understanding convolutional networks[END_REF]. We also mentioned some of the issues related to weights initialization (alleviated with the recent batch-normalization procedure of [START_REF] Ioffe | Batch normalization: Accelerating deep network training by reducing internal covariate shift[END_REF]) and issues related to setting learning rates in the stochastic gradient descent, prompting the usage of adaptive optimizers. Many of the tricks and hacks used for improving the training of neural networks are reported to work well in particular research cases, but the general effectiveness of these methods is not proved by any theory yet, and developing the right intuitions to build high-performance setups is what makes these methods difficult: it is a matter of practice, trial-and-error analysis, and patience.

The introduction of LeCun et al. [1998b] describes this situation in a paragraph that is still true today: "Backpropagation is a very popular neural network learning algorithm because it is conceptually simple, computationally efficient, and because it often works. However, getting it to work well, and sometimes to work at all, can seem more of an art than a science. Designing and training a network using backprop requires making many seemingly arbitrary choices such as the number and types of nodes, layers, learning rates, training and test sets, and so forth. These choices can be critical, yet there is no foolproof recipe for deciding them because they are largely problem and data dependant. However, there are heuristics and some underlying theory that can help guide a practitioner to make better choices."

Conclusion.

In Appendix A, which is the first part of the technical background of this thesis, we showed that the basic building block of machine learning, classification, can be reduced to an optimization problem on a set of parameterized functions, that can be addressed using first-order gradient descent methods.

In this Appendix B, which is the second part, we made an effort to break neural networks down to smaller pieces, pointing out that these methods are conceptually simple, but their practice more difficult due to the high number of hyper-parameters (e.g. number of layers, layer sizes, learning rates) at training time. Our study is of course not exhaustive, but our goal is merely to reveal the true nature of these neural networks: complex and powerful algorithms built from (mostly) simple linear algebra. In the following figures, we show random samples from generators trained with the GAN procedure using the code of [START_REF] Radford | Unsupervised representation learning with deep convolutional generative adversarial networks[END_REF], varying the filter parameters gf and df. We display samples at different epochs (ep) of training. Table C.1 contains the results for the LSUN-Bedrooms dataset [START_REF] Yu | Lsun: Construction of a large-scale image dataset using deep learning with humans in the loop[END_REF]), and Table C.2 for the Labeled Faces in the Wild (LFW, [START_REF] Huang | Labeled faces in the wild: A database for studying face recognition in unconstrained environments[END_REF]) dataset. While the goal is to retrieve the rotation transform that was applied to the data, integration suffers from the curse of dimensionality.

Sinkhorn distances. The Sinkhorn Algorithm, described in [START_REF] Cuturi | Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances[END_REF], Schmitzer explaining our interest in this method.

In our experiments, computations are done on discrete grids of size 128 × 128 representing the square [-2, 2] × [-2, 2] ⊂ R 2 , in order to deal with computational constraints in EMD computation.

Finding the solution. Our model has few parameters, making it possible to perform a grid search over parameters to find the solution. The goal is to find the best rotation angle 𝜃. As described previously, without loss of generality, we use 𝜃 * = 0

for simplicity when generating the data. We observe the tradeoffs due to the different distances being optimized next.

D.3 Results

The obtained solutions, shown in Figures D-6 and D-7, demonstrate that KL and Maximum Likelihood will stretch the rectangle to cover all the data distribution, because the penalty for having a data point not covered by the model is infinite.

Résumé

Les réseaux de neurones à convolution sont des algorithmes d'apprentissage flexibles qui tirent efficacement parti des importantes masses de données qui leur sont fournies pour l'entraînement. Malgré leur utilisation dans des applications industrielles dès les annees 90, ces algorithmes n'ont pas été utilisés pour la reconnaissance d'image à cause de leurs faibles performances avec les images naturelles. C'est finalement grâce a l'apparition d'importantes quantités de données et de puissance de calcul que ces algorithmes ont pu révéler leur réel potentiel lors de la compétition ImageNet, menant à un changement de paradigme en reconnaissance d'image.

La première contribution de cette thèse est une méthode de transfert d'apprentissage dans les réseaux à convolution pour la classification d'image. À l'aide d'une procédure de pré-entraînement, nous montrons que les représentations internes d'un réseau à convolution sont assez générales pour etre utilisées sur d'autres tâches, et meilleures lorsque le pré-entraînement est réalisé avec plus de données.

La deuxième contribution de cette thèse est un système faiblement supervisé pour la classification d'images, pouvant predire la localisation des objets dans des scènes complexes, en utilisant, lors de l'entraînement, seulement l'indication de la présence ou l'absence des objets dans les images.

La troisième contribution de cette thèse est une recherche de pistes de progression en apprentissage non-supervisé. Nous étudions l'algorithme récent des réseaux génératifs adversariaux et proposons l'utilisation d'un test statistique pour l'évaluation de ces modèles. Nous étudions ensuite les liens avec le problème de la causalité, et proposons un test statistique pour la découverte causale. Finalement, grâce a un lien établi récemment avec les problèmes de transport optimal, nous étudions ce que ces réseaux apprennent des données dans le cas non-supervisé.

Mots Clés

Vision artificielle, réseaux de neurones à convolution, apprentissage profond, apprentissage faiblement supervisé, apprentissage non-supervisé, réseaux génératifs adversariaux.

Abstract

Convolutional Neural Networks are flexible learning algorithms for computer vision that scale particularly well with the amount of data that is provided for training them. Although these methods had successful applications already in the '90s, they were not used in visual recognition pipelines because of their lesser performance on realistic natural images. It is only after the amount of data and the computational power both reached a critical point that these algorithms revealed their potential during the Ima-geNet challenge of 2012, leading to a paradigm shift in visual recogntion.

The first contribution of this thesis is a transfer learning setup with a Convolutional Neural Network for image classification. Using a pre-training procedure, we show that image representations learned in a network generalize to other recognition tasks, and their performance scales up with the amount of data used in pre-training.

The second contribution of this thesis is a weakly supervised setup for image classification that can predict the location of objects in complex cluttered scenes, based on a dataset indicating only with the presence or absence of objects in training images.

The third contribution of this thesis aims at finding possible paths for progress in unsupervised learning with neural networks.

We study the recent trend of Generative Adversarial Networks and propose two-sample tests for evaluating models. We investigate possible links with concepts related to causality, and propose a two-sample test method for the task of causal discovery. Finally, building on a recent connection with optimal transport, we investigate what these generative algorithms are learning from unlabeled data.

Figure 1

 1 Figure 1-2: Variability in size, occlusion and truncation: in these images, examples of bicycles can appear partly hidden. Bounding boxes, describing the extent of objects in the images, are shown in yellow. Images from the Pascal VOC dataset (Everingham et al. [2010]).

Figure 1

 1 Figure 1-3: Deformation variability. Animals such as cats can appear in various shapes and poses, adding more difficulty. Images from the Pascal VOC dataset (Everingham et al. [2010]).

Figure 1 - 5 :

 15 Figure 1-5: Example of a classification task : the goal here is to train an algorithm to predict whether an image contains a cat or a dog.

Figure 1 - 6 :

 16 Figure 1-6: An application of classification: Automatic Alternative Text, describing images by listing what concepts are present, for the visually impaired.

Figure 2 - 3 :

 23 Figure 2-3: Empirical models of image variability, by Murase and Nayar [1995]. They introduce pose invariance in recognition by capturing multiple rotated views of objects. At run-time they recognize objects and the closest rotation angle for that view.

Figure 2 - 4 :

 24 Figure 2-4: Example of the material "Crumpled paper"; Leung and Malik [2001] build a vocabulary of 3D textons learned on patches of materials under different lighting conditions, inducing robustness to illumination changes.

Figure 2

 2 Figure 2-5: Schmid and Mohr [1997] propose to describe images using local descriptors, contrasting with global approches such as Eigenfaces. Considering local descriptors allows matching objects in different imaging conditions.

Figure 2 - 6 :

 26 Figure2-6: Given an input area, SIFT[START_REF] David G Lowe | Distinctive image features from scale-invariant keypoints[END_REF]) computes gradients locally (left) then aggregates the information in a 128-bit descriptor (right). Aggregating the gradients from 16 cells provides robustness to small translations.

Figure 2 - 8 :

 28 Figure 2-8: Dataset collected for visual categorization with 7 classes (Csurka et al.[2004]). This method combines the bag-of-visual-words approach with SVM classifiers to perform visual recognition.

Figure 2 - 9 :

 29 Figure 2-9: Example image with the Pascal VOC dataset (Everingham et al. [2010]), with bounding boxes localizing objects, popularizing the task of object detection: recognizing an object class and predicting its extent.

Figure 2 -

 2 Figure 2-10: Spatial pyramids.[START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] propose a pyramidal approach to histogram binning, introducing location-awareness and multi-scale processing in the bag-of-features pipeline.

Figure 2 -

 2 Figure 2-11: Example description of a face.[START_REF] Martin | The representation and matching of pictorial structures[END_REF] propose representing objects as a structure, by assembling parts and connecting them in pairs with a set of "springs".

Figure 2 -

 2 Figure 2-12: Marr and Nishihara [1978], inspired by human vision, propose to decompose objects in a hierarchy of geometric primitives.

Figure 2 -

 2 Figure 2-13: Ioffe and Forsyth [2001] propose detecting limbs as a first step before applying a kinematic model for person detection.

Figure 2 -

 2 Figure 2-14: Fergus et al. [2003b] introduce constellations part models, recognizing objects by detecting visual words (top-right) then evaluating their relative positions against a learned shape model (top-left). Examples shown on the bottom.

Figure 2 -

 2 Figure 2-15: The Dalal & Triggs person detector[START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]), based on Histograms of Gradients. From left to right : (i) input image, (ii) image gradients computed within a grid, (iii) gradients reweighted by the SVM positive weights, (iv) by negative weights. The SVM weights effectively contain a person template for detection.

  2-17) with more flexible deformation models, setting the state of the art for object detection on the Pascal VOC challenge.

Figure 2 -

 2 Figure 2-16: Original caption: Example detection obtained with the person model. The model is defined by a coarse template, several higher resolution part templates and a spatial model for the location of each part. (Figure and caption from the original paper Felzenszwalb et al. [2008].) The Deformable Part-Model approach combines the constellation model with Histograms of Gradients features.

Figure 2 -

 2 Figure 2-17: Original caption: Detections obtained with a 2 component bicycle model. These examples illustrate the importance of deformations mixture models. In this model the first component captures sideways views of bicycles while the secondcomponent captures frontal and near frontal views. The sideways component can deform to match a "wheelie". (Figure and caption from the original paper Felzenszwalb et al. [2010].)

Figure 2 -

 2 Figure 2-18: The objectness approach proposed by Alexe et al. [2010]. Original caption: Desired behavior of an objectness measure. The desired objectness measure should score the blue windows, partially covering the objects, lower than the ground truth windows (green), and score even lower the red windows containing only stuff or small parts of objects.

Figure 2 -

 2 Figure 2-19: Selective search (van de Sande et al.[2011]): pixels in images are initially grouped together with the algorithm of[START_REF] Pedro | Efficient graph-based image segmentation[END_REF], then grouped hierarchically using a data-driven approach before proposing candidate object bounding boxes.

Figure 2 -

 2 Figure 2-20: Frank Rosenblatt with the huge Perceptron (Rosenblatt [1957]), one of the earliest machine vision systems in history.

  vision systems: the Mark I Perceptron (shown in Figure2-20). It can be described as a multi-layer network composed of an input layer composed of 20x20 photosensitive units, an association layer composed of 512 linear threshold units with fixed weights, and an output layer composed of 8 linear threshold units with adaptable weights implemented with stepping motors and trained with the Perceptron algorithm. The Perceptron algorithm allows training a binary classifier by adjusting the weights until finding a suitable hyperplane. This algorithm has been shown to converge on linearly separable data.

Figure 2 -

 2 Figure2-21: The Neocognitron architecture[START_REF] Fukushima | Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position[END_REF]) introduces shiftinvariance into neural networks together with pooling layers (as "complex units" 𝑈 𝐶 ). This multi-layered architecture is very close to the modern neural network architectures that we use today.

Figure 2 -

 2 Figure 2-22: Normalized handwritten digits. This dataset, introduced in LeCun et al. [1989] with the convolution layer, corresponds to the first successful application of convolutional neural networks.

Figure 2 -

 2 Figure 2-23: A digit recognition architecture using convolution layers, as proposed in LeCun et al. [1989]. The convolution kernels on the bottom (H1) allow for extracting edges in the initial image. The multi-convolution kernels (H2) find more complex patterns.

  -24) in non-convex cases. The result of training with SGD depends on the initialization and the order in which the examples are presented.

Figure 2 - 25 :

 225 Figure 2-25: Original caption: Discriminative Viterbi Training GTN Architecture for a character string recognizer based on Heuristic Over-Sergmentation. Quantities in square brackets are penalties computed during the forward propagation. Quantities in parentheses are partial derivatives computed during the backward propagation. Caption and Figure from LeCun et al.[1998a]. The Graph Transformer Networks approach allows for training arbitrarily complex systems in an end-to-end approach as long as the modules are differentiable, generalizing gradient-based learning.

Figure 2 - 26 :

 226 Figure 2-26: The original LSTM recurrent architecture as proposed in Hochreiter[START_REF] Hochreiter | Long short-term memory[END_REF]. The LSTM uses a gating approach to update or output the relevant contents of the hidden state (the Constant Error Carrousel ) in the center.

Figure 2 -

 2 Figure 2-27: The NYU Object Recognition Benchmark (NORB) dataset introduced in LeCun et al. [2004], proposes a large-scale dataset of objects on different backgrounds. With few classes and many examples per class, this is a very favorable case for neural networks, and the unbeatable baseline did not allow the vision community to compete, explaining the little popularity of this dataset.

Figure 2 - 28 :

 228 Figure 2-28: Original caption: Pretraining consists of learning a stack of Restricted Boltzmann machines (RBMs), each having only one layer of feature detectors. The learned feature activations of one RBM are used as the "data" for training the next RBM in the stack. After the pretraining, the RBMs are "unrolled" to create a deep autoencoder, which is then fine-tuned using backpropagation of error derivatives. Caption and Figure from Hinton and Salakhutdinov [2006]. The RBM approach revived interest in deep architectures by offering an initialization method for deep autoencoders.

Figure 2 - 29 :

 229 Figure 2-29:[START_REF] Kavukcuoglu | Learning invariant features through topographic filter maps[END_REF] propose to learn a sparse set of feature detectors that are then arranged into a topographic map (shown here), where similar filters are pooled together to explicitly build invariance to small distortions of the input.

Figure 2 - 30 :

 230 Figure 2-30: Le et al. [2012] train an autoencoder using a distributed system of 10000 CPUs, on frames extracted from YouTube, and observe what individual neurons react strongly to. The first author says: "Perhaps in line with a stereotype about what goes on YouTube, we found a neuron that was highly selective to images of cat faces."

  et al. [2011] stand back from the biologically-plausible saturating sigmoids, and introduce the unbounded ReLU non-linearity (see Figure 2-31), that greatly alleviates the vanishing gradient problem, paving the way for deeper architectures.

Figure 2 - 31 :

 231 Figure 2-31: Biological justification for the Rectifier Linear Unit (ReLU), advocated in Glorot et al. [2011]. Left: biological neurons firing rate as a function of input current. We observe thresholding at the origin. Middle: saturating non-linearities popular at the time. Right: Rectifier Linear Unit and its smoothed version.

Figure 2 - 32 :

 232 Figure 2-32: The LeNet-5 architecture (top, 4-layers deep), proposed in LeCun et al. [1998a], is very close to the more recent AlexNet (bottom, 8-layers deep) architecture, proposed in Krizhevsky et al. [2012].

Figure 2 -

 2 Figure 2-35: Original caption: First column contains query images from ILSVRC-2010 test set, remaining columns contain retrieved images from training set.Figure and caption courtesy of A. Krizhevsky. We can observe in this figure the invariance that is encoded in the CNNs by looking at the nearest neighbors in the corresponding feature space, corresponding to the output of the second fully-connected layer FC7. One may compare this to the invariance encoded in the visual words of Sivic and Zisserman [2003] in Figure 2-7 (bottom) or Fergus et al. [2003b] in Figure 2-14 (top-right).

  Figure 2-35: Original caption: First column contains query images from ILSVRC-2010 test set, remaining columns contain retrieved images from training set.Figure and caption courtesy of A. Krizhevsky. We can observe in this figure the invariance that is encoded in the CNNs by looking at the nearest neighbors in the corresponding feature space, corresponding to the output of the second fully-connected layer FC7. One may compare this to the invariance encoded in the visual words of Sivic and Zisserman [2003] in Figure 2-7 (bottom) or Fergus et al. [2003b] in Figure 2-14 (top-right).

Figure 2 -

 2 Figure 2-36: Screenshots from five Atari 2600 games used by the Deep Q-learning algorithm proposed in Mnih et al. [2013]: Pong, Breakout, Space Invaders, Seaquest, Beam Rider.

Figure 2 -

 2 Figure 2-37: The original R-CNN (Regions with CNN features, Girshick et al. [2014]) algorithm for object detection. The setup first extracts object proposals using the Selective Search algorithm (van de Sande et al. [2011], Figure 2-19), computes a feature transform for each proposal using CNN features and trains a specific object detection classifier on top.The Faster-RCNN[START_REF] Shaoqing Ren | Faster R-CNN: Towards real-time object detection with region proposal networks[END_REF]) variant of this algorithm integrates the object proposal step as a module within a unified network.

Figure 2 -

 2 Figure 2-38: Original caption : The efficiency of ConvNets for detection. During training, a ConvNet produces only a single spatial output (top). But when applied at test time over a larger image, it produces a spatial output map, e.g. 2x2 (bottom). Since all layers are applied convolutionally, the extra computation required for the larger image is limited to the yellow regions. This diagram omits the feature dimension for simplicity.Figure and caption from Sermanet et al. [2014].

  Figure 2-38: Original caption : The efficiency of ConvNets for detection. During training, a ConvNet produces only a single spatial output (top). But when applied at test time over a larger image, it produces a spatial output map, e.g. 2x2 (bottom). Since all layers are applied convolutionally, the extra computation required for the larger image is limited to the yellow regions. This diagram omits the feature dimension for simplicity.Figure and caption from Sermanet et al. [2014].

Figure 2 -

 2 Figure2-39: The Simultaneous Detection and Segmentation (SDS) algorithm proposed in[START_REF] Hariharan | Simultaneous detection and segmentation[END_REF] is very similar to R-CNN[START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF]) but uses object segmentation proposals to address the segmentation task.

Figure 2 -

 2 Figure 2-40: The Fully Convolutional Networks (FCN) approach proposed in Long et al. [2015] consists of assigning an object class to each pixel in the image, not using proposals anymore.

Figure 2 - 41 :

 241 Figure 2-41: The DeepMask algorithm proposed in Pinheiro et al. [2015] consists of training a neural network to predict the segmentation mask of the object in the center of the image, without using proposals.

Figure 2 - 42 :

 242 Figure 2-42: Example outputs of a pose estimation algorithm, DeepPose, proposed in Toshev and Szegedy [2014].

Figure 2 - 43 :

 243 Figure 2-43: Motivation for the approach of Chen and Yuille [2014] for pose estimation. The local appearance of the patch surrounding the elbow can help in predicting the position of the shoulder and the wrist.

Figure 2 -

 2 Figure 2-44: Pfister et al. [2015] adopt a more integrated approach for the task of pose estimation. They propose a neural network architecture that uses appearance and optical flow information to output a pose estimate.

Figure 2 - 45 :

 245 Figure 2-45: The original Pose Machines of[START_REF] Ramakrishna | Pose machines: Articulated pose estimation via inference machines[END_REF] first predict the location of joints from a single image, then refine the predictions in subsequent stages by using contextual features.

Figure 2 -

 2 Figure 2-46: The improved Convolutional Pose Machines of[START_REF] Wei | Convolutional pose machines[END_REF] integrate the prediction and refinement stages within a unified architecture that can be trained end-to-end, resulting in large performance improvements.

Figure 2 -

 2 Figure 2-47: The Stacked Hourglass Network architecture of Newell et al. [2016] for pose estimation, integrating prediction and refinement steps in successive bottomup/top-down steps.

Figure 2 -

 2 Figure 2-48: Wang and Schmid [2013] extract features in videos by following trajectories. In this figure, we can see, in white, trajectories that are considered due to camera motion.

Figure 2 -

 2 Figure 2-49: Tran et al. [2015] propose using spatial-temporal convolution in a neural network to process large datasets of videos and learn transferrable features, extending the approach of Krizhevsky et al. [2012] to the video domain. Original caption (adapted): 2D and 3D convolution operations. a) Applying 2D convolution on a video volume (multiple frames as multiple channels) results in an image. b) Applying 3D convolution on a video volume results in another volume, preserving temporal information of the input signal.

Figure 2 -

 2 Figure 2-50: Simonyan and Zisserman [2014a] propose a Two-Stream architecture for video classification, combining appearance information (Spatial stream) and motion information (Temporal stream) within a single network.

Figure 2 - 51 :

 251 Figure 2-51: Ordonez et al. [2011] propose learning from captioned images available on the Flickr image hosting website in their Im2Text approach. Top row: images and captions from the training set; bottom row: captions selected for query images at test time (good cases). The supervision takes the form of image captions.

Figure 2 -

 2 Figure 2-52: Examples of relationships obtained by the Never Ending Image Learner (NEIL) system of Chen et al. [2013], extracting knowledge from image queries on Google Image Search and clustering similar (according to image features) windows together to obtain bounding boxes for relevant objects. The supervision in this system is obtained by analyzing images corresponding to a similar search query.

Figure 2 -

 2 Figure 2-53: Exemplars by Chum and Zisserman [2007] learned on the Pascal VOC 2006 dataset without bounding box supervision. Original caption: Examples of the exemplar representation for cars side [...]. Models show the spatial distribution of edges and appearance patches. [...] the images below the model show samples from the training images with the automatically learnt ROIs overlaid.

Figure 2 -

 2 Figure 2-55: Building on the efficient sliding idea explained in Sermanet et al. [2014] (see Figure 2-38), we propose a weakly-supervised approach for multi-object classification, that allows predicting the location of objects coarsely in an image using classification score maps at test time. The method will be explained fully in Chapter 4.

Figure 2 -

 2 Figure 2-56: Original caption by Ngiam et al. [2011]: Deep Autoencoder Models. A "video-only" model is shown in (a) where the model learns to reconstruct both modalities given only video as the input. A similar model can be drawn for the "audio-only" setting. We train the (b) bimodal deep autoencoder in a denoising fashion, using an augmented dataset with examples that require the network to reconstruct both modalities given only one. [...]

Figure 2 -

 2 Figure 2-57: Doersch et al. [2015] propose training a neural network to predict the relative configuration of two image patches extracted from an image. Original caption:The algorithm receives two patches in one of these eight possible spatial arrangements, without any context, and must then classify which configuration was sampled.

Figure 2 - 58 :

 258 Figure 2-58:[START_REF] Zhang | Colorful image colorization[END_REF] propose training a neural network to predict the colors of grayscale images as a self-supervised task. At test time, the algorithm is able to colorize legacy pictures.

Figure 2 - 59 :

 259 Figure 2-59: Adversarial examples proposed by Szegedy et al. [2013]. Original caption: Adversarial examples generated for AlexNet.(Left) is a correctly predicted sample, (center) difference between correct image, and image predicted incorrectly magnified by 10x (values shifted by 128 and clamped), (right) adversarial example. All images in the right column are predicted to be an "ostrich, Struthio camelus". Average distortion based on 64 examples is 0.006508. Plase refer to http: // goo. gl/ huaGPb for full resolution images. The examples are strictly randomly chosen. There is not any postselection involved.

  [2015].[START_REF] Radford | Unsupervised representation learning with deep convolutional generative adversarial networks[END_REF], have popularized this idea with promising results on generating new human faces, shown in Figure2-60. As a result of the procedure, GAN generators are able to generate random images resembling a training dataset.

Figure 2 - 60 :

 260 Figure 2-60: Random faces generated by a Generative Adversarial Network architecture. Left: results obtained in early stages of training, right: later stages. Images courtesy of A.B.L. Larsen and S.K. Sønderby (http://torch.ch/blog/2015/11/13/ gan.html).

Figure 2 - 61 :

 261 Figure 2-61: Pathak et al. [2016] propose using an adversarial loss based on a GAN discriminator to improve inpainting. Original caption: Qualitative illustration of the task. Given an image with a missing region (a), a human artist has no trouble inpainting it (b). Automatic inpainting using our context encoder trained with L2 reconstruction loss is shown in (c), and using both L2 and adversarial losses in (d).

  ImageNet classification (which contains more than one million training images) and other smaller-scale computer vision tasks, showing the generality of these pre-trained features for visual recognition. We show directions for improvement by running the pre-training procedure on image data related to the target task. We demonstrate the power of this technique by outperforming the state of the art on the Pascal VOC image classification dataset.

  Figure 3-1: Recognition and localization results of our method for a Pascal VOC test image. Output maps are shown for six object categories with the highest responses. The classification heat maps demonstrate the potential of this setup for localizing objects in images.

  For example, while objects are typically centered in Caltech256 and ImageNet datasets, other datasets such as Pascal VOC and LabelMe are more likely to contain objects embedded in a scene (see Figure3-3). Differences in viewpoints, scene context, "background" (negative class) and other factors, inevitably affect recognition performance when training and testing across different domains[START_REF] Pirsiavash | Detecting activities of daily living in first-person camera views[END_REF],[START_REF] Saenko | Adapting visual category models to new domains[END_REF],[START_REF] Torralba | Unbiased look at dataset bias[END_REF]). Similar phenomena have been observed in other areas such as NLP[START_REF] Jiang | Instance weighting for domain adaptation in NLP[END_REF]). Given the "data-hungry" nature of CNNs and the difficulty of collecting large-scale image datasets, the applicability of CNNs to tasks with limited amount of training data appears as an important open problem. Contributions. To address this problem, we propose to transfer image representations learned with CNNs on large datasets to other visual recognition tasks with limited training data. In particular, we design a method that uses ImageNet-trained layers of CNN to compute efficient mid-level image representation for images in Pascal VOC. We analyze the transfer performance and show significant improvements on the Pascal VOC object and action classification tasks, outperforming the state of the art. We also show promising results for object and action localization. Results of object recognition and localization by our method are illustrated in Figure 3-1.

Figure 3 - 2 :

 32 Figure3-2: Transferring parameters of a CNN. First, the network is trained on the source task (ImageNet classification, top row) with a large amount of available labelled images. Pre-trained parameters of the internal layers of the network (C1-FC7) are then transferred to the target tasks (Pascal VOC object or action classification, bottom row). To compensate for the different image statistics (type of objects, typical viewpoints, imaging conditions) of the source and target data we add an adaptation layer (fully connected layers FCa and FCb) and train them on the labelled data of the target task.

  Figure 3-3: Illustration of different dataset statistics between the source (ImageNet) and target (Pascal VOC) tasks. Pascal VOC data displays objects embedded in complex scenes, at various scales (right), and in complex mutual configurations (middle). Left: Image from ImageNet with label maltese terrier. Middle and right: Images from Pascal VOC with label dog.

  on the ImageNet classification source task. Each image typically contains one object centered and occupying significant portion of the image with limited background clutter as illustrated in Figure 3-3(left). The network is trained to predict the ImageNet object class label given the entire image as input. Details are given in Section 3.3.

Figure 3

 3 Figure 3-4: Example cars from the ImageNet dataset. The cars are generally centered and scaled to the size of the image.

Figure 3

 3 Figure 3-6: Tiling an image at multiple scales builds patches where objects are centered and scaled, closer to the average appearance in ImageNet.

Figure 3

 3 Figure 3-7: As a result of our tiling procedure, we obtain a large number of patches that we need to label appropriately.

  At test time we apply the network to each of the (approximately) 500 overlapping multi-scale patches extracted from the test image. Examples of patch scores visualized over entire images are shown in Figures 3-1 and 3-9 -3-10. We use the following aggregation formula to compute the overall score for object 𝐶 𝑛 in the image score(𝐶 𝑛 ) = 1 𝑀 𝑀 ∑ 𝑖=1 𝑦(𝐶 𝑛 |𝑃 𝑖 ) 𝑘 , (3.1) where 𝑦(𝐶 𝑛 |𝑃 𝑖 ) is the output of the network for class 𝐶 𝑛 on image patch 𝑃 𝑖 , 𝑀 is the number of patches in the image, and 𝑘 ≥ 1 is a parameter. Higher values of 𝑘 focus on the highest scoring patches and attenuate the contributions of low-and mid-scoring patches. The value of 𝑘 = 5 was optimized on the validation set and is fixed in our experiments.

  this section we first describe details of training, and discuss pre-training results for the source task of ImageNet object classification. We next show experimental results of the proposed transfer learning method on the target Pascal VOC object classification task for both VOC 2007 and VOC 2012 datasets. We also investigate the dependency of results on the overlap of source and target tasks by object classes. Finally, we apply the proposed transfer learning method on a very different task of action recognition in still images. Training convolutional networks. All our training sessions were carried out using the code provided by Krizhevsky et al. [2012] and replicating their exact dropout and jittering strategies. However, we do not alter the RGB intensities and we use a single GeForce GTX Titan GPU with 6GB of memory instead of the two GPUs of earlier generation as originally used. The training procedure periodically evaluates the cross-entropy objective function on a subset of the training set and on a validation set. The initial learning rates are set to 0.01 and the network is trained until the training cross-entropy is stabilized. The learning rates are then divided by 10 and the training procedure repeats. We stop training after three iterations. We have not tuned parameters for this part of the algorithm and we did not observe overfitting on the validation set.

  Action recognition. The Pascal VOC 2012 action recognition task consists of 4588 training images and 4569 test images featuring people performing actions among ten categories such as jumping, phoning, playing instrument or reading. This finegrained task differs from the object classification task because it entails recognizing fine differences in human poses (e.g. running v.s. walking) and subtle interactions with objects (phoning or taking photo). Training samples with multiple simultaneous actions are excluded from our training set. To evaluate how our transfer method performs on this very different target task, we use a network pre-trained on 1512 ImageNet object classes and apply our transfer methodology to the Pascal VOC action classification task. Since the bounding box of the person performing the action is known at testing time, both training and testing are performed using a single square patch per sample, centered on the person bounding box. Extracting the patch possibly involves enlarging the original image by mirroring pixels. The results are summarized in row Pre-1512 (Table

  Figures 3-9 -3-10 clearly demonstrate that the network provides an estimate of the action location in the image.

  Figure 3-9: Response maps on representative images of several categories of the VOC 2012 object and action classification test set. The rightmost column contains the highest-scoring false positive (according to our judgement) for each of these categories. Note that correct estimates of object and action locations and scales are provided by the score maps.

  [2011]) to outperform object detection algorithms.3. Razavian et al.[2014] do a survey and advocate the use of CNNs as a feature transform available "off-the-shelf", allowing replacing SIFT/HoG and their Fisher Vector representations with CNN feature vectors collected in the FC layers.

  Figure 4-1: Evolution of localization score maps for the motorbike class over iterations of our weakly-supervised CNN training. Note that the network learns to localize objects despite having no object location annotation at training, just object presence/absence labels. Note also that locations of objects with more usual appearance (such as the motorbike shown in left column) are discovered earlier during training.

  image-level labels only, localizes objects or their distinctive parts in training images, as illustrated in Figure4-1. So, is object localization with convolutional neural networks for free? In this chapter we set out to answer this question and analyze the developed weakly supervised CNN pipeline on two object recognition datasets containing complex cluttered scenes with multiple objects.Contributions. The contributions of this work are twofold. First, we develop a weakly supervised convolutional neural network end-to-end learning pipeline that learns from complex cluttered scenes containing multiple objects by explicitly searching over possible object locations and scales in the image. Second, we perform an extensive experimental analysis of the network's classification and localization performance on the Pascal VOC 2012 and the much larger Microsoft COCO datasets.

First, we treat

  the fully connected layers as convolutions, which allows us to deal with nearly arbitrary-sized images as input. Second, we explicitly search for the highest scoring object position in the image by adding a single global max-pooling layer at the output. Third, we use a cost function that can explicitly model multiple objects present in the image. The three modifications are discussed next and the network architecture is illustrated in Figure 4-2.

Figure 4 - 2 :

 42 Figure 4-2: Network architecture for weakly supervised training. We convert the Fully Connected layers FCa and FCb to the corresponding Convolution layers Ca and Cb. The score maps are then globally pooled: only the largest output is kept as an image-level class score.

1Figure 4 - 3 :

 43 Figure 4-3: Multiscale object recognition.

a

  separate binary classification problem for each class. The loss function is therefore a sum of k binary logistic regression losses, one for each of the k classes 𝑘 ∈ {1 • • • k}, ℓ( 𝑓 𝑘 (x) , 𝑦 𝑘 ) = ∑ 𝑘 log(1 + 𝑒 -𝑦 𝑘 𝑓 𝑘 (x) ) , (4.1) where 𝑓 𝑘 (x) is the output of the network for input image x and 𝑦 𝑘 ∈ {-1, 1} is the image label indicating the absence/presence of class 𝑘 in the input image x. Each class score 𝑓 𝑘 (x) can be interpreted as a posterior probability indicating the presence of class 𝑘 in image x with transformation

Figure 4 - 4 :

 44 Figure 4-4: Illustration of the weakly-supervised learning procedure. At training time, given an input image with an aeroplane label (left), our method increases the score of the highest scoring positive image window (middle), and decreases scores of the highest scoring negative windows, such as the one for the car class (right).

  this section we describe details of the training procedure. Similar to Chapter 3 we pre-train the convolutional feature extraction layers C1-C7 on images from the ImageNet dataset and keep their weights fixed. This pre-training procedure is standard and similar to Krizhevsky et al. [2012]. Next, the goal is to train the adaptation layers Ca and Cb using the Pascal VOC or MS COCO images in a weakly supervised manner, i.e. from image-level labels indicating the presence/absence of the object in the image, but not telling the actual position and scale of the object. This is achieved by stochastic gradient descent training using the network architecture and cost function described in Section 4.2, which explicitly searches for the best candidate position of the object in the image using the global max-pooling operation. We also search over object scales (similar to Papandreou et al. [2015]) by training from images of different sizes. The training procedure is illustrated in Figure 4-2. Details and further discussion are given next.

  We apply the proposed method to the Pascal VOC 2012 object classification task and the more recent released Microsoft COCO dataset. The Pascal VOC 2012 dataset contains 5k images for training, 5k for validation and 20 object classes. The much larger COCO dataset contains 80k images for training, 40kimages for validation and 80 classes. On the COCO dataset, we wish to evaluate whether our method scales-up to much bigger data with more classes.We use Torch7(Collobert et al. [2011a]) for our experiments. For Pascal VOC, we use a network pre-trained on 1512 classes of ImageNet following Chapter 3; for COCO, we use the Overfeat[START_REF] Sermanet | Overfeat: Integrated recognition, localization and detection using convolutional networks[END_REF]) network. Training the adaptation layers was performed with stochastic gradient descent (learning rate 0.001, momentum 0.9).Pascal VOC 2012 classification results. In Table4.1, we provide classification scores on the Pascal VOC 2012 test set, for which many baseline results are available. Evaluation is performed via the Pascal VOC evaluation server. The per-class performance is measured using average precision (the area under the precision-recall curve) and summarized across all classes using mean average precision (mAP). Our weakly supervised approach (g.Weak sup) obtains the highest overall mAP among all single network methods outperforming other CNN-based methods trained from image-level supervision (c-g) as well as the comparable setup of Chapter 3 (b) that uses object-level supervision.4.5.2 DiscussionBenefits of sliding-window training. Here we compare the proposed weakly supervised method (g. Weak sup) with training from full images (f. Full images), where no search for object location during training/testing is performed and images are presented to the network at a single scale. Otherwise the network architectures are identical. Results for Pascal VOC test data are shown in Table 4.1). The results clearly demonstrate the benefits of sliding window multi-scale training attempting to localize the objects in the training data. The largest improvements are obtained for small objects, such as bottles and potted plants, where AP increases by 15-20%. Similar results on the COCO dataset are shown in the first row of Figure 4-5, where sliding window weakly supervised training (blue) consistently improves over the full image training (red) for all classes. Benefits of multi-scale training and testing. On the COCO dataset, multiscale training improves the classification mAP by about 1% when compared to training at a single-scale 𝑠 = 1. The intuition is that the network gets to see objects at different scales, increasing the overall number of examples. Scanning at multiple scales at test time provides an additional 3% increase in classification mAP.Does adding object-level supervision help classification? Here we investigate whether adding object-level supervision to our weakly supervised setup improves classification performance. In order to test this, we remove the global max-pooling layer in our model and introduce a "masked pooling" layer that indicates the location of individual objects during training. In detail, the masked pooling layer uses ground truth maps of the same size as the output of the network, signaling the presence or absence of an object class to perform the global max-pooling, but now restricted to the relevant area of the output. This provides learning guidance to the network as the max-scoring object hypothesis has to lie within the ground truth object location in the image. We have also explored a variant of this method, that minimized the object score outside of the masked area to avoid learning from the context of the object, but obtained consistently worse results. Classification results for the maskedpooling method (i. Masked pool) on both the Pascal VOC and COCO datasets are provided in Table4.2 and show that adding this form of object-level supervision does not bring significant benefits over the weakly-supervised learning.

  u m b r e ll a : 6 0 .7 3 1 . h a n d b a g : 3 7 .7 3 2 . ti e : 6 6 .6 3 3 . s u it c a s e : 3 7 .0 3 4 . fr is b e e : 4 7 .9 3 5 . s k is : 8 6 .3 3 6 . s n o w b o a r d : 4 7 .7 3 7 . s p o r ts b a ll : 6 6 .8 3 8 . k it e : 8 1 .2 3 9 . b a s e b a ll b a t : 7 8 .4 4 0 . b a s e b a ll g lo v e : 8 r e fr ig e r a to r : 5 4 .2 8 4 . b o o k : 4 9 .9 8 5 . c lo c k : 7 1 .9 8 6 . v a s e : 5 8 .3 8 7 . s c is s o r s : 1 9 .0 8 8 . te d d y b e a r : 7 0 .8 8 9 . h a ir d r ie r : 1 .8 9 0 . to o th b r u s h : 2 8 .6

Figure 4 - 5 :

 45 Figure 4-5: Per-class barplots of the output scores on the Microsoft COCO validation set. From top to bottom : (a) weakly-supervised classification AP (blue) vs. full-image classification AP (red). (b) weakly-supervised classification AP (blue) vs. weakly-supervised location prediction AP (green). (c) weakly-supervised location prediction AP (green) vs. masked-pooling location prediction AP (magenta). At the bottom of the figure, we provide the object names and weakly-supervised classification AP values.

Figure 4 - 6 :

 46 Figure 4-6: Example location predictions for images from the Microsoft COCO validation set obtained by our weakly-supervised method. Note that our method does not use object locations at training time, yet can predict locations of objects in test images (yellow crosses). The method outputs the most confident location per object per class.

  Figure5-2: How GANs work: A generator 𝑔 maps a noise space 𝒵 to an image space 𝒳 (usually RGB images). A discriminator 𝑑 is trained to classify between real samples and fake samples 𝑔(𝒵). At each step, the model computes the gradient of the loss: the discriminator decreases it to classify better; the generator increases it to generate more real-looking samples, making the task of the discriminator harder.

Figure 5 - 3 :

 53 Figure 5-3: Examples of 64 × 64 pixel images from Radford et al. [2016]. Top: samples of new faces generated by a Deep Convolutional GAN. Middle: Result of interpolation in noise space 𝒵: we observe a transition from one bedroom sample to the next. Bottom: example of vector arithmetic. Authors perform arithmetic in the input space noise vectors and generate the examples on the right, hinting at a structured model of face pictures.

Figure 5 - 4 :

 54 Figure5-4:[START_REF] Isola | Image-to-image translation with conditional adversarial networks[END_REF] propose a method that maps input images to new generated images, allowing a GAN to reproduce the image processing task defined by the dataset.

  [2015]) and DCGANs 3[START_REF] Radford | Unsupervised representation learning with deep convolutional generative adversarial networks[END_REF]) propose models generating faces that look somewhat realistic, while not being always perfectly coherent. We show examples in Figure5-3.In this figure, it is clear that the generated faces (top) are much sharper than those obtained with alternative approches such as Variational Autoencoders[START_REF] Diederik | Auto-encoding variational bayes[END_REF]), shown in Figure5-1. Interestingly, the model shows evidence of a certain level of understanding of the data: it can perform arithmetic on the latent noise space and obtain meaningful outputs in terms of attributes, as shown in the bottom example where man with glasses -man + woman = woman with glasses.While GANs use no meta-data or labels,[START_REF] Mirza | Conditional generative adversarial nets[END_REF] propose a variant named "Conditional GAN " that considers data pairs (𝑐, 𝑥) to generate new images following conditions: Conditional GANs use an input 𝑐 (e.g. an image) and a noise vector 𝑧 to generate a new image 𝑥 through a generator function 𝑔 : (𝑐, 𝑧) ↦ → 𝑥, while the discriminator 𝑑 : (𝑐, 𝑥) ↦ → [0, 1] also has access to the conditioning variable.

Figure 5 - 5 :

 55 Figure 5-5: Checkerboard artifacts appear (top) as a result of an architecture based on deconvolutions. Using a different architecture alleviates this problem (bottom). Figure from Odena et al. [2016].

Figure 5 - 6 :

 56 Figure 5-6: First row: Face from the training dataset (left) and face generated by a Deep Convolutional GAN (right). Second row: output maps of the first convolution layer for the real face. Third row: same output maps for the generated face. While the generated face does not show visible artifacts, some appear clearly as horizontal and vertical lines, especially on the two leftmost maps.

Figure 5

 5 Figure 5-8: Statistical footprint of causality. We consider the case 𝑌 ← 𝑓 (𝑋) + 𝐸, where 𝑋 and 𝐸 are independent uniform variables, and 𝑓 is a linear function. We plot (𝑋, 𝑌 ) on the left and (𝑌, 𝑋) on the right and illustrate the variance of the noise with red bars. The noise has uniform variance only in the direction 𝑋 → 𝑌 , which is therefore the preferred causal direction. Plots obtained from: Lopez-Paz [2016].

Figure 5

 5 Figure 5-9: A marionette, with a plate controlling it. The position of the limbs depends on the position of the plate, up to noise and momentum from previous motion.

Figure 5 -

 5 Figure 5-11: Examples from the dataset we built from screenshots of our puppet simulator. The limb configuration of the puppet, attached to the plate with strings, depends on the position of the colored plate.

Figure 5 -

 5 Figure5-12: Samples generated by our DCGAN trained on our puppet dataset. In many cases, the position of the puppet does not depend on the position of the plate: we highlight with the same color samples where this phenomenon can be clearly observed.

Figure 5 -

 5 Figure 5-15: Example plots of the data in the Tüebingen cause-effect pairs dataset. From left to right: (i) x: horsepower, y: acceleration, x→y; (ii) x: age, y: height, x→y; (iii) x: ozone, y: temperature, x←y; (iv) x: life expectancy, y: latitude, x←y.

Figure 5 -

 5 Figure 5-16: Original caption: An isotropic Gaussian distribution was fit to data drawn from a mixture of Gaussians by either minimizing Kullback-Leibler divergence (KLD), maximum mean discrepancy (MMD), or Jensen-Shannon divergence (JSD). The different fits demonstrate different tradeoffs made by the three measures of distance between distributions.Figure and caption from Theis et al. [2016]. MMD (Maximum Mean Discrepancy) refers to[START_REF] Gretton | A kernel method for the two-sample-problem[END_REF] and is a kernel-based method for measuring a distance between distributions (used in Section 5.3 as a two-sample test).

Figure 5 -Figure 5

 55 Figure 5-18: Our uniform rectangle distribution model. This model has three parameters, width (a), height (b) and rotation angle (𝜃).

  Adversarial training. Adversarial training has potential, as shown by their successful applications in computer vision. However we have no good understanding of the result of this training process. In Chapter 5, we investigate what GANs learn,

Figure A- 2 :

 2 Figure A-2: Reducing the detection task to a classification problem. The goal is to find a tight bounding box around the bottle. We sample possible locations, reducing the task to binary classification predicting whether the input window contains completely and predominantly the object of interest.

Figure A- 3 :

 3 Figure A-3: Reducing the tracking task to a classification problem. The goal is to follow an object in a video. We sample windows in the neighborhood of the object of interest in the first frame, and train a classifier to predict whether one of the new windows contains the same object.

Figure A- 4 :

 4 Figure A-4: Illustration of overfitting. In this case we build a function to match data points (in black) following a noisy linear distribution. The overfitted red curve matches the training points better but the less flexible blue curve seems to match the structure of the overall data better: we expect it to fit new points better.

  will be erroneous even on the examples that were seen during training. On the other hand, if the capacity is too high, the classifier will learn the labels for the training examples by heart and will output random predictions on new unknown examples, while still minimizing the empirical risk measured on training data. A classifier will work properly if it has just the right amount of capacity: enough to learn the general redundant patterns in the data, but not enough to learn infrequent example-specific patterns irrelevant to the task.

Figure

Figure A- 7 .

 7 Figure A-7. This figure exposes the problem of local minima and asymptotic plateaus.

Figure A- 7 :

 7 Figure A-7:[START_REF] Bottou | Stochastic gradient learning in neural networks[END_REF] (updated in[START_REF] Bottou | Online algorithms and stochastic approximations[END_REF]) provides a convergence proof of SGD towards extremal points (shown here). We observe different kinds of extremal points; from left to right: local minimum, local maximum, global minumum, asymptotic plateau. Figure credit[START_REF] Bottou | Online algorithms and stochastic approximations[END_REF].

  Geometric view. Let 𝑊 and 𝑋 be two non-zero vectors in R 𝑑 . These two vectors define a two-dimensional subspace (at least one) that contains both. Let (𝑒 1 , 𝑒 2 ) be an orthonormal basis of this plane, such that 𝑊 = ||𝑊 || 𝑒 1 , where ||.|| is the Euclidean norm. In this case, the dot-product is equal to:𝑌 = (𝑊 |𝑋) = ||𝑊 || ||𝑋|| cos(𝜃), (B.4)where 𝜃 is the angle in ] -𝜋, 𝜋] between 𝑊 and 𝑋 in this 2D plane. The angle 𝜃 measures how much 𝑊 and 𝑋 point to the same direction, as shown in Figure B-1.

  Figure B-2:Computing dot-products between many vectors (𝑎 𝑖 ) 𝑖 and many vectors (𝑏 𝑗 ) 𝑗 can be seen as a matrix multiplication operation for which there are extremely optimized algorithms available, e.g. OpenBLAS (http://www.openblas.net) on CPU or cuBLAS (https://developer.nvidia.com/cublas) on nVidia GPUs, often close to the limits of the hardware.

Figure B- 3

 3 Figure B-3. A neural network is an arrangement of modules such that the input is processed, in a sequence, by a composition of functions. The example shown corresponds to the following function 𝑓 , after adding the weights (Figure B-4). Given 𝑓 1 , 𝑓 2 , 𝑓 3𝑎 , 𝑓 3𝑏 , 𝑓 4 , one defines ŷ as follows:

f 4 L

 4 Figure B-3: An example architecture made of 5 nodes laid out on a Directed Acyclic Graph (DAG).

Figure B- 4 :

 4 Figure B-4: The same architecture as in Figure B-3, with details exposed, in particular the parameters 𝑤 𝑖 .

Forward propagation .

 propagation We can evaluate the prediction ŷ = 𝑓 (𝑤, 𝑥) by traversing the graph in the forward direction. The layers in this graph use the outputs of other layers as inputs (except for the first). Since the graph is directed and acyclic, layers can be topologically sorted (see FigureB-6) and evaluated individually in a sequence until the output is reached, where we collect the prediction ŷ.Backpropagation. Backpropagation is the algorithm that allows computing the gradients within a DAG of layers. Given the loss gradient 𝜕𝐿 𝜕 ŷ , we traverse the sorted graph backwards, propagating the loss gradient at each step to the layers, then to their weights, as we illustrate in FigureB-7.

Figure B- 5 :

 5 Figure B-5: The operations performed by a layer. In black, the forward operations for evaluating the output of the layer. In red and green, operations related to gradient computation.𝜕𝑓 𝑖 𝜕𝑤 𝑖 and

Figure B- 6 :

 6 Figure B-6: Topologically sorted graph corresponding to the example in Figure B-3.When the graph is directed and acyclic, it can be traversed in order, which allows forward (going right) and backward propagation (going left). Topological sorting ensures that all the outputs of the parents are available to their children when they are evaluated.

f 4 L

 4 Figure B-7: Backpropagation. The loss function L uses ground truth annotations to provide gradient with respect to the predictions ŷ. This gradient is then propagated (in red) in the network. Each layer can then compute the gradient with respect to its weights (in green) as shown in Figure B-5.

Figure

  Figure B-8: The fully-connected layer takes its input 𝑋 and applies a matrix-vector operation with the weight matrix 𝑊 and adds a bias vector 𝐵. We show the corresponding operations for computing the gradients on the right. Hatched rectangles are gradients of the loss. Each value in 𝑌 depends on all the values of 𝑋, hence fully-connected.

  Figure B-9: Non-linear activation functions used commonly in neural networks. Top: Sigmoid: 𝜎(𝑥) = 1 1 + 𝑒 -𝑥 . Middle : Hyperbolic tangent: tanh(𝑥) = 𝑒 𝑥 -𝑒 -𝑥 𝑒 𝑥 + 𝑒 -𝑥 . Bottom : Rectified Linear Unit: ReLU(𝑥) = max(0, 𝑥).ReLU is non-saturating and allows propagating gradient easily at the cost of unbounded activation. Sigmoid and Tanh can make gradient vanish if the activation is in the flat gradient regime.224

  figure.

Figure

  Figure B-10: A 5 × 5 pixel RGB image (left) can be seen as a 3 × 5 × 5 tensor (right).We call the sizes of the tensor width, height, and depth as shown. Feature maps are concatenated over the depth dimension. Indexing of tensor elements is done such that for 𝑥 𝑎𝑏𝑐 , 𝑎 corresponds to the depth dimension, 𝑏 to the height dimension, 𝑐 to the width dimension.

Figure

  Figure B-12 shows a simple cell grid, of size 2 and stride 2.Figure B-13 shows a

  Figure B-12 shows a simple cell grid, of size 2 and stride 2.Figure B-13 shows a more complicated overlapping pooling grid, of size 3 and stride 2.

Figure

  Figure B-11: Pooling operations consist of two steps: decomposing the input in a grid depending on parameters called the size (here 3) and the stride (here 2), then processing each cell with a function 𝑓 to obtain an element of the output. In this illustration, we have 𝑦 11 = 𝑓 (𝑥 11 . . . 𝑥 33 ), 𝑦 12 = 𝑓 (𝑥 13 . . . 𝑥 35 ), and so on.

Figure B- 12 :

 12 Figure B-12: We show an example of a grid of size 2 and stride 2 used to cover an input of size 4 × 4.

Figure B- 13 :

 13 Figure B-13: We show an example of an overlapping grid of size 3 and stride 2 used to cover an input of size 5 × 5.

Figure B- 14 :

 14 Figure B-14: Different pooling operations. Left: Original Grace Hopper image. Middle: result of max-pooling with grid of size 5, stride 4. Right: result of average-pooling with the same grid. We upscale the results to allow for comparison with the original image. Some details, such as the contours of the coat, appear sharper in the max-pooling case and blurrier with average-pooling.

  Figure B-16:A convolution layer takes an input tensor 𝑋, consisting of 𝑛 𝑓 𝑒𝑎𝑡𝑢𝑟𝑒𝑠 concatenated feature maps, and processes it with 𝑛 𝑘𝑒𝑟𝑛𝑒𝑙𝑠 kernels 𝑊 𝑖 and biases 𝑏 𝑖 to obtain independent feature maps, concatenated into an output 𝑌 .

  Figure B-17: Example output of a convolution layer with ReLU nonlinearity applied on an RGB image. On each row: input image, convolution kernel and output. We see that the top kernel extracts diagonal sharp edges (top-left to bottom-right). The bottom kernel extracts smoother horizontal edges.

Figure B- 18 :

 18 Figure B-18: Forward computation of the convolution layer for a single kernel 𝑊 . We extract the cells corresponding to the grid, similarly to the pooling operations. Then, for each position (𝑖, 𝑗), the cell 𝐶(𝑖, 𝑗) is used in a dot-product with the kernel 𝑊 ; we add a bias 𝑏 to obtain the output value 𝑦 𝑖𝑗 .

  Figure B-19: Input gradient computation of the convolution layer for a single kernel 𝑊 . We use number values for clarity in the grid-summing operation. We first compute the gradient corresponding to each cell 𝜕𝐿 𝜕𝐶(𝑖, 𝑗) = 𝜕𝐿 𝜕𝑦 𝑖𝑗 𝑊 .Then, we sum the contributions back into the input gradient 𝜕𝐿 𝜕𝑋 following the grid.

Figure B- 21 :

 21 Figure B-21: Seeing the convolution operation as a matrix multiplication. The convolution layer is based on dot-products between many cells and many weighted kernels.Arranging the cells into a matrix (of size (𝑛 𝑐𝑒𝑙𝑙𝑠 × cell dimensionality)), and the kernels into another matrix (of size (𝑛 𝑘𝑒𝑟𝑛𝑒𝑙𝑠 × cell dimensionality)) allows using efficient generic linear algebra routines such as the matrix multiplication. The result of this matrix multiplication is then rearranged into a tensor, exposing concatenated feature maps.

Figure B- 22 :

 22 Figure B-22: Reading the AlexNet architecture (figure from[START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF]). The blocks correspond to the data tensors processed by the network. The convolution and fully-connected (dense) layers are the operators between the blocks. The network contains a total of 60 million parameters.

Figure

  tensor: 224 × 224 × 3 (RGB input image) (a) Convolution conv1: 96 kernels of size 11 × 11, stride 4 55 × 55 × 96 (b) ReLU nonlinearity 55 × 55 × 96 2. Data tensor: 55 × 55 × 96 (a) Max-Pooling pool1: size 3, stride 2 27 × 27 × 96 (b) Convolution conv2: 256 kernels of size 5 × 5, stride 1 27 × 27 × 256 (c) ReLU nonlinearity 27 × 27 × 256 3. Data tensor: 27 × 27 × 256 (a) Max-Pooling pool2: size 3, stride 2 13 × 13 × 256 (b) Convolution conv3: 384 kernels of size 3 × 3, stride 1 13 × 13 × 384 (c) ReLU nonlinearity 13 × 13 × 384 4. Data tensor: 13 × 13 × 384 (a) Convolution conv4: 384 kernels of size 3 × 3, stride 1 13 × 13 × 384 (b) ReLU nonlinearity 13 × 13 × 384 5. Data tensor: 13 × 13 × 384 (a) Convolution conv5: 256 kernels of size 3 × 3, stride 1 13 × 13 × 256 (b) ReLU nonlinearity 13 × 13 × 256 6. Data tensor: 13 × 13 × 256 (a) Max-Pooling pool5: size 3tensor: 1000 (one score per ImageNet class)

  subset is called the receptive field. Stacking convolution layers increases the receptive field of elements of feature maps as we progress in the network, as we show in FigureB-23. As a result, the input image to a network is first processed locally then more globally by the further layers. This gives convolutional neural networks a bottom-up structure that may be related to their success.

  Figure B-23: Stacking two convolution layers increases the receptive field of an element of the feature map. In this example, each output element of the first layer has access to a 3 × 3 area, but the second layer has access to a 3 × 3 square of these elements, giving it access to a 5 × 5 area of the input image.

Figure B- 24 :

 24 Figure B-24: Original caption: Visualization of features in a fully trained model. Forlayers 2-5 we show the top 9 activations in a random subset of feature maps across the validation data, projected down to pixel space using our deconvolutional network approach. Our reconstructions are not samples from the model: they are reconstructed patterns from the validation set that cause high activations in a given feature map. For each feature map we also show the corresponding image patches. Note: (i) the strong grouping within each feature map, (ii) greater invariance at higher layers and (iii) exaggeration of discriminative parts of the image, e.g. eyes and noses of dogs (layer 4, row 1, cols 1). Best viewed in electronic form. Figure and caption from Zeiler and Fergus [2014].

  backward signal remain approximately the same throughout the network with hyperbolic tangent activations. As a result, the neurons activate in areas where the slope of the saturating nonlinearity is high (the linear regime, corresponding to the central part of the plots in Figure B-9 (top and middle)). Current frameworks implement such initialization schemes natively.Batch normalization. The batch normalization layer was proposed in Ioffe andSzegedy [2015] and alleviates issues related to these weight scaling issues. When a mini-batch of inputs is processed, the statistics of activations are computed across the mini-batch and the data representation is centered on-the-fly (zero-mean, unitvariance across the mini-batch) before the nonlinearity, within a differentiable procedure. In the saturating cases, this ensures that activations lie mostly on the linear regime, avoiding vanishing and exploding signals in the forward and backward computations. In all cases, authors report faster, easier and better training; this technique is very popular as of 2017.

Figure B- 25 :

 25 Figure B-25: Illustration of typical loss curves for an AlexNet ImageNet training. The training and validation losses decrease over iterations, and when they reach a plateau the learning rate (initially 10 -2 ) is manually decreased by a factor 10 (pointed with arrows), until the procedure converges.

Figure B- 26 :

 26 Figure B-26: Data augmentation. An input image undergoes a label-preserving transformation: we crop pixels in the border of the image and flip the result horizontally with 50% probability during trianing, creating more examples for the neural network to learn. This technique does not correspond to an explicit regularization term in the objective function but reduces overfitting.

FigureFigure B- 28 :

 28 Figure B-27: A recurrent unit processing an input sequence (𝑥 𝑖 ) 𝑖 , updating a hidden state sequence (ℎ 𝑖 ) 𝑖 with a recurrent connection, producing an output sequence (𝑦 𝑖 ) 𝑖 .

251 6 .

 6 Output RGB image tensor: 64 × 64 × 3 DC-GAN discriminator architecture with parameter df: 1. Image input: 64 × 64 × 3 (a) Convolution c1: (df) kernels of size 4 × 4, stride 1 (b) Spatial Batch Normalization (c) ReLU non-linearity 2. State dimensionality: 32 × 32 × df (a) Convolution c2: (2×df) kernels of size 4 × 4, stride 2 (b) Spatial Batch Normalization (c) ReLU non-linearity 3. State dimensionality: 16 × 16 × (2 × df) (a) Convolution c3: (4×df) kernels of size 4 × 4, stride 2 (b) Spatial Batch Normalization (c) ReLU non-linearity 4. State dimensionality: 8 × 8 × (4 × df) (a) Convolution c4: (8×df) kernels of size 4 × 4, stride 2 (b) Spatial Batch Normalization (c) ReLU non-linearity 5. State dimensionality: 4 × 4 × (8 × df) (a) Convolution dc5: 1 kernel of size 4 × 4 (b) Sigmoid nonlinearity 6. Output score: 1 scalar value

  Figure D-1: The central limit theorem says that sums of independent variables tend to be gaussian. One way of finding the independent components is to find a direction such that the sample distribution is maximally non-gaussian. The graphs are taken from the ICA book[START_REF] Hyvarinen | Independent component analysis[END_REF]).

Figure D- 2 :

 2 Figure D-2: Our two-dimensional parabola-based data distribution. Left: 3D plot seen from above, middle: from the side, right: heatmap and colormap.

Figure D- 3 :

 3 Figure D-3: Points sampled from the parabola distribution shown above.

Figure D- 4 :

 4 Figure D-4: Our data distribution with sampling noise. Left: 3D plot seen from above, middle: from the side, right: heatmap and colormap.

[

  2016],[START_REF] Chizat | Scaling Algorithms for Unbalanced Transport Problems[END_REF], lets us compute an "entropy-regularized" version of the EMD in an efficient way. As the regularization parameter becomes smaller, the Sinkhorn distance should converge to the EMD. We use code from the Python Optimal Transport library 1 that we ported to Torch.The example shown in Figure5-17 (main text) computes optimal transport from a grid of dimensionality 32 × 32 = 1024 to another grid of dimensionality 1024. Even though we use a GPU-based implementation of Sinkhorn Distances, computation requires several seconds in this low-resolution case. Optimal transport is computationally heavy, but in the GAN scenario, using the Kantorovitch duality and optimizing through 1-Lipschitz functions appears tractable as shown by[START_REF] Arjovsky | To appear in ICML[END_REF],

  Large scale recognition. With the growing computational power and amount of images on the Internet, interest emerges for recognition on a large scale. The Ima-

	geNet dataset (Russakovsky et al. [2015]) appears in 2009 with more exploitable data
	than ever available before for learning. In 2011, ImageNet contains 14 million labeled
	images corresponding to more than 21 thousand classes. The proposed challenge con-
	sists of performing image classification using a dataset of a million images from 1000
	classes with varying levels of granularity (notably 120 different breeds of dogs).
	With this new challenge, computer vision adapts new methods. Perronnin et al.

[2010] introduce new techniques for describing features, in order to cope with large sets of images, using Fisher Kernels in a Gaussian Mixture Model framework with computationally efficient linear classifiers. Fisher Vectors were involved in many of best-performing state-of-the-art methods, in the ImageNet Challenge of 2011 2 .

With the perspective of larger datasets, research in object detection witnessed the introduction of objectness methods for candidate windows: building on different image cues (e.g. color contrast or edge density)

[START_REF] Alexe | What is an object? In Computer Vision and Pattern Recognition[END_REF]

(further improved in

[START_REF] Alexe | Measuring the objectness of image windows[END_REF]

) propose a generic objectness measure describing how likely it is for a window to contain an object rather than background or a small parts of objects, as shown in Figure

2

-18. Following the objectness approach, van de Sande et al.

[2011]

propose Selective Search window proposals (see Figure

2

-19) to build a state-of-the-art object detector.

  candidates are then processed by a trainable neural network 𝑇 𝑟𝑒𝑐 , returning a score for each class, building the interpretation graph 𝐺 𝑖𝑛𝑡 . Then, the left branch uses ground truth labels to keep only the correct paths in the constrained graph 𝐺 𝑐 , and searches the shortest path (smallest penalty) with the Viterbi algorithm, building 𝐺 𝑐𝑣𝑖𝑡 . In parallel, the right branch searches the shortest path from 𝐺 𝑖𝑛𝑡 directly without the path selector supervision, and builds 𝐺 𝑣𝑖𝑡 . The difference in penalties of the shortest paths returned in 𝐺 𝑐𝑣𝑖𝑡 and 𝐺 𝑣𝑖𝑡 are then compared to obtain the value of the loss.During training, the gradient is propagated through the active edges of these

graphs. The left branch propagates positive gradient to correct candidates through the shortest path of the constrained graph 𝐺 𝑐𝑣𝑖𝑡 , and the right branch propagates negative gradient through the shortest path of the unconstrained graph 𝐺 𝑣𝑖𝑡 . As a result of this procedure, the recognition network 𝑇 𝑟𝑒𝑐 receives gradient for learning.

The left branch ensures that the correct candidates are learned, while the right branch penalizes all candidates. If a candidate is present in both branches (in 𝐺 𝑐𝑣𝑖𝑡 and 𝐺 𝑣𝑖𝑡 )

  This bar graph shows the results of the 5 best performing teams on ILSVRC-2012. The methods perform classification on 1000 mutually exclusive classes, and five guesses are allowed for each test example (hence "top-5 error rate %"). We observe that the SuperVision team[START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF]) outperforms all others by a dramatic margin. Figure credit: Rob Fergus.

	Figure 2-33: Datasets commonly used for neural networks research.
	Left: MNIST, introduced in LeCun et al. [1998a], 60000 training examples, 10000
	testing examples, 28 × 28-pixels binary images, 10 classes. Right: CIFAR-10, introduced in Krizhevsky [2009], 50000 training examples, 10000 testing examples, 32 × 32-pixels RGB images, 10 classes. layer on GPUs at unprecedented speeds, around 100 times faster than CPU versions. As this type of layer accounts for the vast majority of computations in a CNN, a fast Figure 2-34: et al. [2012] propose using an 8-layer deep convolutional network later named AlexNet
	2.3.1 Scaling up neural networks implementation is a key to process large natural images. This code, ready and public (shown in Figure 2-32) in a purely supervised manner. This network is very similar
	early 2012 4 , provides a crucial component to the success of CNNs: computational to the original neural networks of the '90s. A few important details are tuned for the GPU convolution. Krizhevsky [2009], explores methods to build better features using unsupervised methods and introduces the labeled CIFAR-10 dataset. It cor-power. problem: non-linearities are switched to ReLUs (Glorot et al. [2011]), and specific
	normalization layers and regularization methods (weight decay, data augmentation) responds to a "natural image" version of the MNIST digits dataset introduced in ImageNet. As mentioned in Section 2.1, the ImageNet dataset (Russakovsky et al. are added to combat overfitting. This setup, powered by GPUs and a large amount of LeCun et al. [1998a], with images of similar size (around 32 × 32), about the same [2015]) is proposed in 2009 and exceeds in size all previous manually labeled datasets. labeled data, outperforms all the state-of-the-art computer vision methods by a wide number of samples (around 60000), also split in 10 classes but with RGB images (see In 2011, ImageNet contains 14 million high-resolution images corresponding to more margin in the 2012 competition, as shown in Figure 2-34, inducing a major paradigm Figure 2-33). performance of neural networks tends to increase with the amount of training data, The standard MNIST digit classification dataset, commonly used for evaluating than 21 thousand classes. We show examples of these images in Figure 2-35. As the shift in computer vision that we discuss next.
	neural networks, was too easy, and error levels below 1% were already reached when ImageNet provides a second crucial component: large amounts of labeled data.
	it was introduced by LeCun et al. [1998a]. In contrast, the CIFAR-10 dataset offers The ImageNet Large Scale Visual Recognition Challenge (ILSVRC) is the cor-
	a higher level of difficulty and is closer to natural images, but still allows quick responding annual competition; it consists of performing image classification using
	experimentation on neural networks like MNIST. a dataset of a million images from 1000 classes. For ILSVRC-2012, Krizhevsky
	In his work, A. Krizhevsky writes cuda-convnet, implementing the multi-convolution

  [START_REF] Chen | Neil: Extracting visual knowledge from web data[END_REF], extracting knowledge from image queries on Google Image Search and clustering similar (according to image features) windows together to obtain bounding boxes for relevant objects. The supervision in this system is obtained by analyzing images corresponding to a similar search query.

	box around it. This is an important setup for many practical applications as (weak)
	image-level annotations are often readily available in large amounts. Guillaumin et al.
	[2009] use text tags and propagate them to new images to perform automatic anno-
	tation; Ordonez et al. [2011] use image captions available on the Flickr image hosting
	website (see Figure 2-51) to match similar images and propose relevant captions;

  Table 3.2: Per-class results for object classification on the VOC2012 test set (average precision %). NUS-PSL relates to the work of Yan et al. [2012].Image classification on Pascal VOC 2007. We apply our mid-level feature transfer scheme to the Pascal VOC 2007 object classification task. Results are reported in Table 3.1. Our transfer technique (Pre-1000C) demonstrates significant Image classification on Pascal VOC 2012. We next apply our method to the Pascal VOC 2012 object classification task. Results are shown in the row Pre-Conversely, we have augmented the 1,000 classes of the ILSVRC-2012 training set with 512 additional ImageNet classes selected to increase the overlap with specific classes in the Pascal VOC target task. We included all the ImageNet classes located below the hoofed mammal (276 classes), furniture (165), motor vehicle (48), Action jump phon instr read bike horse run phot comp walk mAP Stanford pas [2012]75.7 44.8 66.6 44.4 93.2 94.2 87.6 38.4 70.6 75.6 69.1

	Image classification on ImageNet. We first train a single convolutional network on the 1000 classes and 1.2 million images of the ImageNet 2012 Large Scale Visual Recognition Challenge (ILSVRC-2012). This network has exactly the same structure as the network described in Krizhevsky et al. [2012]. Layers FC6 and FC7 have 4096 units. Training lasts about one week. The resulting network achieves a 18% top-5 error rate 1 , comparable to the 17% reported by Krizhevsky et al. [2012] for a single Inria 77.5 63.6 56.1 71.9 33.1 60.6 78.0 58.8 53.5 42.6 54.9 45.8 77.5 64.0 85.9 36.3 44.7 50.6 79.2 53.2 59.4 NUS-PSL 82.5 79.6 64.8 73.4 54.2 75.0 77.5 79.2 46.2 62.7 41.4 74.6 85.0 76.8 91.1 53.9 61.0 67.5 83.6 70.6 70.5 Pre-1000C 88.5 81.5 87.9 82.0 47.5 75.5 90.1 87.2 61.6 75.7 67.3 85.5 83.5 80.0 95.6 60.8 76.8 58.0 90.4 77.9 77.7 NUS-PSL 97.3 84.2 80.8 85.3 60.8 89.9 86.8 89.3 75.4 77.8 75.1 83.0 87.5 90.1 95.0 57.8 79.2 73.4 94.5 80.7 82.2 Pre-1000C Pre-1000R Pre-1512 No pretrain 85.2 75.0 69.4 66.2 48.8 82.1 79.5 79.8 62.4 61.9 49.8 75.9 71.4 82.7 93.1 59.1 69.7 49.3 80.0 76.7 70.9 93.5 78.4 87.7 80.9 57.3 85.0 81.6 89.4 66.9 73.8 62.0 89.5 83.2 87.6 95.8 61.4 79.0 54.3 88.0 78.3 78.7 93.2 77.9 83.8 80.0 55.8 82.7 79.0 84.3 66.2 71.7 59.5 83.4 81.4 84.8 95.2 59.8 74.9 52.9 83.8 75.7 76.3 improvements over previous results on this data outperforming the 2007 challenge winners Marszalek et al. [2007] (Inria) by 18.3% and the more recent work of Song et al. [2011] (Nus-psl) by 7.2%. public transport (18), bicycle (5) nodes of the WordNet hierarchy. In order to ac-commodate the larger number of classes, we also increased the size of the FC6 and FC7 layers from 4,096 to 6,144 dimensions. Training on the resulting 1.6 million images achieves a 21.8% top-5 error rate on the 1,512 classes. Using this pre-trained Oxford pas [2012] 77.0 50.4 65.3 39.5 94.1 95.9 87.7 42.7 68.6 74.5 69.6 No pretrain 43.2 30.6 50.2 25.0 76.8 80.7 75.2 22.2 37.9 55.6 49.7 Pre-1512 73.4 44.8 74.8 43.2 92.1 94.3 83.4 45.7 65.5 66.8 68.4 Pre-1512U 74.8 46.0 75.6 45.3 93.5 95.0 86.5 49.3 66.7 69.5 70.2 94.6 82.9 88.2 84.1 60.3 89.0 84.4 90.7 72.1 86.8 69.0 92.1 93.4 88.6 96.1 64.3 86.6 62.3 91.1 79.8 82.8 Table 3.3: Pascal VOC 2012 action classification results (AP %).

network. This slight performace loss could be caused by the absence of RGB intensity manipulation in our experiments.

plane bike bird boat btl bus car cat chair cow table dog horse moto pers plant sheep sofa train tv mAP Table

3

.1: Per-class results for object classification on the VOC2007 test set (average precision %).

Inria relates to the work of

[START_REF] Marszalek | Learning object representations for visual object class recognition[END_REF]

, and NUS-PSL to the work of

[START_REF] Song | Contextualizing object detection and classification[END_REF]

.

plane bike bird boat btl bus car cat chair cow table dog horse moto pers plant sheep sofa train tv mAP 1000C of Table

4

.1. Although these results are on average about 4% inferior to those reported by the winners of the 2012 challenge (NUS-PSL -

[START_REF] Yan | Generalized hierarchical matching for sub-category aware object classification[END_REF]

), our method outperforms

[START_REF] Yan | Generalized hierarchical matching for sub-category aware object classification[END_REF]

on five out of twenty classes. To estimate the performance boost provided by the feature transfer, we compare these results to the performance of an identical network directly trained on the Pascal VOC 2012 training data (No pretrain) without using any external data from ImageNet. Notably, the performance drop of nearly 8% in the case of No pretrain clearly indicates the positive effect of the proposed transfer.

Transfer learning and source/target class overlap. Our source ILSVRC-2012 dataset contains target-related object classes, in particular, 59 species of birds and 120 breeds of dogs related to the bird and dog classes of Pascal VOC. To understand the influence of this overlap on our results, we have pre-trained the network on a source task data formed by 1,000 ImageNet classes selected, this time, at random among all the 22,000 available ImageNet classes. Results of this experiment are reported in Table

4

.1, row Pre-1000R. The overall performance has decreased slightly, indicating that the overlap between classes in the source and target domains may have a positive effect on the transfer. Given the relatively small performance drop, however, we conclude that our transfer procedure is robust to changes of source and target classes.

As the number of training images in this experiment was about 25% smaller than in the ILSVRC-2012 training set (Pre-1000C), this could have been another reason for the decrease of performance. network we have obtained further improvements on the target task, outperforming the winner of Pascal VOC 2012

[START_REF] Yan | Generalized hierarchical matching for sub-category aware object classification[END_REF]

) on average (row Pre-1512 in Table 4.1). In particular, improvements are obtained for categories

(cow, horse, sheep, sofa, chair, table)

related to the added classes in the source task. By comparing results for Pre-1000R, Pre-1000C and Pre-1512 setups, we also note the consistent improvement of all target classes. This suggests that the number of images and classes in the source task might be decisive for the performance in the target task.

Hence, we expect further improvements by our method using larger source tasks.

Varying the number of adaptation layers. We have also tried to change the number of adaptation layers in the best performing PRE-1512 training set-up. Using only one fully connected adaptation layer FCb of size 21 (the number of categories) results in about 1% drop in performance. Similarly, increasing the number of adaptation layers to three (of sizes 2048, 2048 and 21, respectively) also results in about 1% drop in classification performance. Object localization. Although our method has not been explicitly designed for the task of localization, we have observed strong evidence of object and action localization provided by the network at test time. For qualitative assessment of localization results, we compute an output map for each category by averaging the scores of all the testing patches covering a given pixel of the test image. Examples of such output

  Object-level sup. plane bike bird boat btl bus car cat chair cow table dog horse moto pers plant sheep sofa train tv mAP Image-level sup. plane bike bird boat btl bus car cat chair cow table dog horse moto pers plant sheep sofa train tv mAP Table 4.1: Single method image classification results on the VOC 2012 test set. Methods

	a.Nus-SCM 97.3 84.2 80.8 85.3 60.8 89.9 86.8 89.3 75.4 77.8 75.1 83.0 87.5 90.1 95.0 57.8 79.2 73.4 94.5 80.7 82.2	b.Oquab 94.6 82.9 88.2 84.1 60.3 89.0 84.4 90.7 72.1 86.8 69.0 92.1 93.4 88.6 96.1 64.3 86.6 62.3 91.1 79.8 82.8	c.Z&F 96.0 77.1 88.4 85.5 55.8 85.8 78.6 91.2 65.0 74.4 67.7 87.8 86.0 85.1 90.9 52.2 83.6 61.1 91.8 76.1 79.0	d.Chatfield 96.8 82.5 91.5 88.1 62.1 88.3 81.9 94.8 70.3 80.2 76.2 92.9 90.3 89.3 95.2 57.4 83.6 66.4 93.5 81.9 83.2	e.Nus-HCP 97.5 84.3 93.0 89.4 62.5 90.2 84.6 94.8 69.7 90.2 74.1 93.4 93.7 88.8 93.2 59.7 90.3 61.8 94.4 78.0 84.2	f.Full Images 95.3 77.4 85.6 83.1 49.9 86.7 77.7 87.2 67.1 79.4 73.5 85.3 90.3 85.6 92.7 47.8 81.5 63.4 91.4 74.1 78.7	g.Weak Sup 96.7 88.8 92.0 87.4 64.7 91.1 87.4 94.4 74.9 89.2 76.3 93.7 95.2 91.1 97.6 66.2 91.2 70.0 94.5 83.7 86.3	a,b use object-level supervision. Methods c to	g use image-level supervision only. The combination of methods e reaches 90.3% mAP (in Wei et al. [2014]), the highest reported a and	b.Oquab: Chapter 3, c.Z&F: Zeiler a.Nus-SCM: Song et al. [2011], result on this data at the time of these experiments. References:	and Fergus [2014],

d.Chatfield: Chatfield et al. [2014], e.Nus-HCP: Wei et al. [2014],

  Table 4.2: Classification and location prediction mean Average Precision on the validation sets for Pascal VOC and COCO datasets. *For R-CNN[START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF]), which is an algorithm designed for object detection, we use only the most confident bounding box proposal per class and per image for evaluation.

	Setup	Classification	Location Prediction
	Dataset	VOC	COCO	VOC	COCO
	h.Full images	76.0	51.0	-	-
	i.Masked pool	82.3	62.1	72.3	42.9
	j.Weak sup	81.8	62.8	74.5	41.2
	k.Center pred.	-	-	50.9	19.1
	l.RCNN*	79.2	-	74.8	-

  plane bike bird boat btl bus car cat chair cow table dog horse moto pers plant sheep sofa train tv mAP i.Masked pool 89.0 76.9 83.2 68.3 39.8 88.1 62.2 90.2 47.1 83.5 40.2 88.5 93.7 83.9 84.6 44.2 80.6 51.9 86.8 64.1 72.3 j.Weak sup 90.3 77.4 81.4 79.2 41.1 87.8 66.4 91.0 47.3 83.7 55.1 88.8 93.6 85.2 87.4 43.5 86.2 50.8 86.8 66.5 74.5 k.Center pred. 78.9 55.0 61.1 38.9 14.5 78.2 30.7 82.6 17.8 65.4 17.2 70.3 80.1 65.9 58.9 18.9 63.8 28.5 71.8 22.4 51.0 l.RCNN* 92.0 80.8 80.8 73.0 49.9 86.8 77.7 87.6 50.4 72.1 57.6 82.9 79.1 89.8 88.1 56.1 83.5 50.1 81.5 76.6 74.8 Table 4.3: Location prediction scores on the VOC12 validation set. Maximal responses are labeled as correct when they fall within a bounding box of the same class, and count as false negatives if the class was present but its location was not predicted. We then use the confidence values of the responses to generate precision-recall values.

  Pa(𝑋 𝑖 , 𝒢), 𝑁 𝑖 ) for all 𝑖 = 1, . . . , 𝑑 (5.6) where 𝒢 is a Directed Acyclic Graph (DAG) with vertices associated to each of the random variables 𝑋 1 , . . . , 𝑋 𝑑 , Pa(𝑋 𝑖 , 𝒢) denotes the set of random variables which are parents of 𝑋 𝑖 in the graph 𝒢, 𝑁 𝑖 is an independent noise random variable that follows the probability distribution 𝑃 (𝑁 𝑖 ). Then, we say that 𝑋 𝑖 → 𝑋 𝑗 if 𝑋 𝑖 ∈ Pa(𝑋 𝑗 ), since a change in 𝑋 𝑖 will cause a change in 𝑋 𝑗 , as described by the 𝑗-th SE.

Table 5 .

 5 . 1: Results on cause-effect discovery on the Tübingen cause-effect pairs dataset. This dataset, and the ANM-HSIC and IGCI methods are provided by[START_REF] Mooij | Distinguishing cause from effect using observational data: methods and benchmarks[END_REF]. RCC corresponds to the work of[START_REF] Lopez-Paz | Towards a learning theory of cause-effect inference[END_REF] and NCC toLopez-Paz et al. [2017].

	Method	ANM-HSIC IGCI RCC NCC CGAN-C2ST Ensemble C2ST type
				73%	82%	KNN
	Accuracy	67%	71% 76% 79%	70%	73%	NN
				58%	65%	MMD

  ∃𝐴, 𝐵 ≥ 0, E 𝑧 [𝐻(𝑧, 𝑤) 2 ] ≤ 𝐴 + 𝐵(𝑤 -𝑤 * ) 2 .If the update rule for (𝑤 𝑡 ) 𝑡 is:𝑤 𝑡+1 = 𝑤 𝑡 -𝛾 𝑡 𝐻(𝑧, 𝑤 𝑡 ),

				(A.29)
	Let (𝛾 𝑡 ) 𝑡 be a sequence such that:
	∑	𝛾 2 𝑡 < ∞,		(step sizes decrease fast enough)
	∑	𝛾 𝑡 = ∞.		(step sizes allow traveling arbitrary distances in R 𝑑 )
				(A.30)
	then
		lim 𝑡	𝑤 𝑡	𝑎.𝑠.

→ 𝑤 * (optimization succeeds almost surely).

(A.31)

  We saw in Section B.1 that for a dot-product 𝑦 𝑖𝑗 = (𝑊 |𝐶(𝑖, 𝑗)), deriving the gradients

	gives:	𝜕𝑦 𝑖𝑗 𝜕𝐶(𝑖, 𝑗)	= 𝑊 , and	𝜕𝑦 𝑖𝑗 𝜕𝑊	= 𝐶(𝑖, 𝑗). For backpropagation, we first compute the
	gradient for each cell (	𝜕𝐿 𝜕𝑦 𝑖𝑗	is a scalar):
					𝜕𝐿 𝜕𝐶(𝑖, 𝑗)	=	𝜕𝐿 𝜕𝑦 𝑖𝑗	𝜕𝑦 𝑖𝑗 𝜕𝐶(𝑖, 𝑗)	=	𝜕𝐿 𝜕𝑦 𝑖𝑗	𝑊	(B.21)
	then sum the contributions of each cell within a tensor	𝜕𝐿 𝜕𝑋	of same size as the input,
							x 111 x 112 x 113 x 111 x 112 x 113
		x 11 x 12 x 13 x 14 x 11 x 12 x 13 x 14				x 121 x 122 x 123 x 121 x 122 x 123
		x 21 x 22 x 23 x 24 x 21 x 22 x 23 x 24 x 41 x 42 x 43 x 44 x 31 x 32 x 33 x 34 x 31 x 32 x 33 x 34				x 111 x 112 x 113 x 121 x 122 x 123 x 121 x 122 x 123 x 111 x 112 x 113 x 131 x 132 x 133 x 131 x 132 x 133	1 3
							x 131 x 132 x 133 x 131 x 132 x 133
							x 111 x 112 x 113 x 111 x 112 x 113
							x 121 x 122 x 123 x 121 x 122 x 123
							x 131 x 132 x 133 x 131 x 132 x 133
							Cell gradients

by following the grid, adding up the overlapping portions, as shown in Figure B-19:

  0, (B.28)ℎ 𝑖+1 = 𝑓 ℎ (𝑥 𝑖+1 , ℎ 𝑖 , 𝑤 ℎ ), (B.29) 𝑦 𝑖 = 𝑓 𝑜𝑢𝑡 (ℎ 𝑖 , 𝑤 𝑜𝑢𝑡 ) (B.30)where 𝑤 ℎ and 𝑤 𝑜𝑢𝑡 are the parameters of the recurrent unit, (ℎ 𝑖 ) 𝑖 is a sequence of hidden states, (𝑥 𝑖 ) 𝑖 is an input sequence, and (𝑦 𝑖 ) 𝑖 is an output sequence. We show in FigureB-27 an illustration of a recurrent unit.

		h i+1 = f h (x i+1 ,h i ,w h )
	Input sequence (x 1 ,...,x n )	Hidden states (h i )	y i =f out (h i, w out )	Output sequence (y 1 ,...,y n )

In

2013, 350 million pictures were uploaded on Facebook every day.http://www. businessinsider.com/facebook-350-million-photos-each-day-2013-9

https://code.facebook.com/posts/457605107772545/

[START_REF] Schmid | Local grayvalue invariants for image retrieval[END_REF] is the only reference in the introduction

http://image-net.org/challenges/LSVRC/2011/results

Yann Le Cun reports an unfair bias against neural networks methods in a withdrawal letter from the CVPR conference in 2012 https://plus.google.com/+YannLeCunPhD/posts/gurGyczzsJ7

http://code.google.com/p/cuda-convnet/

https://www.wired.com/2013/03/google_hinton/

https://research.googleblog.com/2015/08/the-neural-networks-behind-google-voice. html

https://www.wired.com/2013/12/facebook-yann-lecun/

https://code.facebook.com/posts/289921871474277

https://code.facebook.com/posts/457605107772545

https://techcrunch.com/2014/01/26/google-deepmind/

Optical flow encodes the underlying motion information between a pair of neighboring video frames.

Not related to the next paragraph.

5 guesses are allowed.

http://docs.nvidia.com/cuda/cublas.

Code package available at: https://github.com/qassemoquab/texfuncs

http://torch.ch.

We do simple interpolation in our experiments.

Laplacian Pyramid of Generative Adversarial Networks

Deep Convolutional Generative Adversarial Networks

The second term in the JS divergence (Equation

5.10) only considers the support of Q, and its value decreases when the density estimates match better.

This derivation is similar to the one proposed in[START_REF] Goodfellow | Generative adversarial nets[END_REF].

See Equation (5.20) in the next paragraph.

The value of 𝑚 determines the Lipschitz constant 𝐾, and this leads to minimizing 𝐾.𝑊 1 , or more precisely an approximation because of the restrictions on 𝑓 .

With the notations of Section B.2, if layer 𝑖 is a fully-connected layer, then 𝑤 𝑖 is a vector containing all the values in 𝑊 and 𝐵.

A max-pooling layer, which will be described in the next section, is also non-linear.

It can happen when a ReLU nonlinearity outputs 0, but in this case the propagated gradient is multiplied by 0 and doesn't cause issues.

https://github.com/rflamary/POT

fell inside one of the ground truth bounding boxes of that object (if multiple object instances were present). This metric differs from the standard object detection bounding box overlap metric as it does not take into account whether the extent of the object is predicted correctly and it only measures localization performance for one object instance per image. Note however, that even this type of location prediction is very hard for complex cluttered scenes considered in this work.

Location prediction results. The summary of the location prediction results for both the Pascal VOC and Microsoft COCO datasets is given in Table 4.2. The perclass results for the Pascal VOC and Microsoft COCO datasets, are shown in Table 4.3 (j.Weak sup) and Figure 4-5 (green bars), respectively.

Center prediction baseline. We compare the location prediction performance to the following baseline. We use the max-pooled image-level per-class scores of our weakly supervised setup (j.Weak sup), but predict the center of the image as the location of the object. As shown in Table 4.2, using the center prediction baseline (k.Center pred.) results in a >50% performance drop on COCO, and >30% drop on Pascal VOC, compared to our weakly supervised method (j.Weak sup) indicating the difficulty of the location prediction task on this data.

Comparison with R-CNN baseline. In order to provide a baseline for the location prediction task, we used the bounding box proposals and confidence values obtained with the state-of-the-art object detection R-CNN [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF]) algorithm on the Pascal VOC 2012 validation set. Note that this algorithm was not designed for classification, and its goal is to find all the objects in an image, while our algorithm looks only for a single instance of a given object class. To make the comparison as fair as possible, we process the R-CNN results to be compatible with our metric, keeping for each class and image only the best-scoring bounding box proposal and using the center of the bounding box for evaluation. Results are summarized in Table 4.2 and the detailed per-class results are shown in Table 4.3. Interestingly, our weakly supervised method (j.Weak sup) achieves comparable location predic-Second, the gradient 𝜕𝑊 1 𝜕𝑓 of the 𝑊 1 objective is a scalar with fixed unit-magnitude (it is +1 for real samples and -1 for generated samples) with respect to the potential 𝑓 (𝑥) of a sample provided by the output of the discriminator. As a consequence, this procedure greatly stabilizes the training.

Third, in the adversarial training procedure, the critic 𝑓 is trained for 5 to 10 consecutive steps for each training step of the generator 𝑔, in order to approximately satisfy the supremum search in Equation 5.19.

Applying a restriction to the magnitude of the weight parameters ensures that the discriminator is Lipschitz-continuous with constant K (depending on the value of 𝑚). But we note that while the Kantorovitch-Rubinstein dual formulation (Equation 5.18) considers the set of all 1-Lipschitz functions, WGAN uses a set that depends on the discriminator architecture. As we saw previously with the derivation of the JS divergence from the ℱ-divergence, restricting the set of functions in WGAN also leads to an approximation to the optimal transport criterion being minimized.

The point of view of optimal transport. This approach gives valuable insights into the problem of matching two distributions by connecting it to optimal transport and distances. Distances are an important notion in the context of learning a distribution of images as we expect a meaningful semantic distance to be small for images containing the same object; for example, this is not true for the pixelwise L 2 distance: slightly translating an object can significantly increase this distance between two images while the content remains almost identical because foreground pixels and background pixels do not have the same semantic importance.

We recall that the Lipschitz-continuity of a real-valued function 𝑓 in a metric space (with metric function 𝑑) corresponds to the following inequality:

where K is the Lipschitz constant. Currently, the WGAN weight constraint ensures that the discriminator output varies slowly if the value of a pixel in the input is and between distributions of images for a clearer understanding of the unsupervised learning problem.

181

Technical background

We want to provide technical background for this thesis, that we split in two parts:

Appendix A on Machine Learning, and Appendix B on Neural Networks. We will:

• show that many computer vision problems can be cast as classification problems (Appendix A).

• explain that classification corresponds to an optimization problem in machine learning, that can be addressed using first-order gradient descent methods on parameterized functions (Appendix A).

• describe neural networks as a particular restriction of the set of differentiable functions that fits in this learning framework (Appendix B).

• detail how backpropagation works in a neural network architecture and what are the necessary conditions (Appendix B).

• provide examples of important layers that are commonly used in neural networks (Appendix B).

Appendix A

Technical background -Supervised

Classification for visual recognition

Outline

In this first part, we want to explain the classification problem, and an approach to solve it. The goal is to introduce in the context of machine learning:

• data distributions, that we want to understand,

• classifiers, that are algorithms trained to make sense of data,

• objective functions, that allow a learning setup to use data from the real world,

• parameterized classifier functions, of which neural networks are a special case,

• stochastic gradient descent, which is the algorithm used to train neural networks.

In Section A.1, we will first describe the data that we use for classification, and

show that in supervised learning, the knowledge present in the data is an illustration of the procedure that was used to collect it. In particular, the data may contain biases, and requires human agreement on the labeling.

pairs (𝑥, 𝑦) ∼ 𝑝(𝑥, 𝑦) is called building a dataset. The goal is to build a function 𝑓 ∈ ℱ := 𝒳 → 𝒴 that provides predictions ŷ = 𝑓 (𝑥). We want the machine to mimic human understanding and predict ŷ = 𝑦.

A dataset is a finite set of examples (𝑥 𝑖 , 𝑦 𝑖 ) 𝑖 sampled from 𝑝(𝑥, 𝑦). For example, we can sample examples from the set 𝒳 of images of pets, with corresponding labels in the label space 𝒴 = {𝑐𝑎𝑡, 𝑑𝑜𝑔}. For simplicity, we will assume that there are no other pets than cats and dogs.

Supervised learning consists of learning the conditional distribution 𝑝(𝑦|𝑥) using the dataset: in this example, this means that given an image 𝑥 ∈ 𝒳 , the machine should be able to output whether this image is of a cat or of a dog, on new samples from the input space 𝒳 (images of pets that were not seen before). In order to do this, we expect a learning machine to learn the redundant patterns in the data, and associate them with the relevant label to provide a prediction on new samples. There is a catch though: the dataset distribution 𝑝(𝑥, 𝑦) carries a lot of hidden information (and possible patterns) related to the way it was collected, which may be ultimately absorbed by the machine during learning.

A.1.2 Biases due to human intervention.

As mentioned above, building a dataset consists of collecting samples from the data distribution 𝑝(𝑥, 𝑦) = 𝑝(𝑦|𝑥)𝑝(𝑥). Human intervention occurs in the following steps:

• defining the input space 𝒳 : in our case, selecting only images of pets is a restrictive condition.

• Collecting the samples 𝑥: in our example, browsing the internet for collecting images implies that other people have put these images online in the first place, following unknown rules that are carried by the distribution 𝑝(𝑥).

• Defining the label space 𝒴: in our example, the {cat, dog} set implies that pets should be grouped in these two large categories, but it is also possible to use the set {{breeds of cats}, {breeds of dogs}} in this setting. The label space 𝒴

A.2.2 Generality of classification in vision problems

Classification is ubiquitous in computer vision, especially whenever some form of recognition is involved: many tasks can be broken down and reduced to a combination of binary classification tasks. We review some examples below to illustrate that classification is a base building block for many computer vision setups.

Example: Image classification. The base task of image classification consists of predicting whether an image contains, or not, at least one object of a given class.

In completely and predominantly an object. This approach corresponds to the R-CNN algorithm [START_REF] Girshick | Rich feature hierarchies for accurate object detection and semantic segmentation[END_REF]) for object detection.

Similarly, object segmentation can be cast as a classification problem by considering all possible windows in an image and training a classifier to answer whether the

Conclusion

Classification is a base building block in computer vision, that is ubiquitous when it comes to visual recognition. Problems can often be reduced to binary classification, making it a very general case.

A.3 Optimization and learning

We described how general the classification problem is, and we are now interested in the method for solving it. The common approach is to have a dataset and optimize a classifier with respect to a continuous loss function, allowing the use of first-order (gradient) methods. In the following, we assume that we have a finite dataset 𝒟:

In this expression (𝑥 𝑖 , 𝑦 𝑖 ) are sample/label pairs following a distribution 𝑝(𝑥, 𝑦).

A.3.1 Empirical Risk Minimization.

We are interested in finding a function that will provide the correct prediction for any sample from the distribution 𝑝(𝑥). In order to evaluate this function, we will use a loss function ℓ to compare its predictions to the ground truth label. For instance, in binary classification, we can define the 0-1 loss function ℓ 0-1 to reflect the performance metric (see Section A.2) we are interested in:

where ŷ is a prediction (ŷ = 𝑓 (𝑥)), and 𝑦 is a ground truth label. A lower value of loss is better. This loss function indicates if the classifier made an error. Since we want to maximize the amount of correct predictions over the data, we want to minimize this loss over the data distribution. We define the risk associated to the classifier 𝑓

Conclusion

We show that learning is done by defining a loss (or cost) function over a training set, and finding the best function (the one with the lowest loss) within a restricted set of functions ℱ. Choosing this set of functions is done by imposing restrictions that have an effect on the capacity of the classifier. In order to use optimization methods such as gradient descent, we choose in practice a set of functions that are continuously differentiable with respect to their set of parameters 𝑤.

A.4 Gradient-based algorithms

The ideal case for optimization is to have a functional 𝐶 to minimize (which corresponds to the empirical risk or the objective function), and a set of parameters 𝑤 such that 𝐶 is differentiable and convex w.r.t. 𝑤:

where ℓ is a loss function, and 𝑓 is a classifier function. In this case, it is possible to use gradient descent to find 𝑤 * = argmin

The convexity assumption is generally not met in practice, especially with neural networks; yet we will see in Section A.5, that it is still possible to learn with a nonconvex functional 𝐶 if it is differentiable and meets certain properties.

A.4.1 Continuous loss functions

We can not perform gradient descent directly on the 0-1 loss function defined in Section A.3 because it is neither continuous nor differentiable. However, it is possible to use continuous approximations for learning.

Surrogate loss functions. We can approximate the 0-1 loss with one of the following functions (plots in predictions:

Hinge loss: ℓ ℎ𝑖𝑛𝑔𝑒 (ŷ, 𝑦) = max(0, 1 -𝑦 ŷ), (A.9)

(A.10)

These surrogate loss functions are differentiable, which is useful for gradient descent.

We choose one and call it ℓ. Learning a classifier consists, then, in solving the following optimization problem:

Using a continuous surrogate loss function implies that the classifier 𝑓 outputs values in R instead of 𝒴 (in the case of binary classification). The classification decision can then be obtained via a post-processing step (such as thresholding the result).

Conclusion.

In order to solve the optimization problem of minimizing the empirical risk, we use a continuous approximation of the loss function described in Section A.3. This lets us build an objective function; adding terms to this objective function steers training towards a set of solutions. In particular, regularization penalties involve tradeoffs between the various terms in the objective function such as sacrificing accuracy on the training set in order to obtain better performance on unseen examples, which is effective in practice for reducing overfitting.

A.5 Learning with gradient descent

The optimization problem described above can be solved using first-order (gradient descent) methods. We describe here the convergence theorems that we have and introduce stochastic gradient descent, which is the most common method for training neural networks. Gradient descent is an example of optimization algorithm that can be used to find a minimizer 𝑤 * of a differentiable convex function 𝐶(𝑤). The underlying concept is simple:

• for any set of parameters 𝑤 𝑡 in a sequence, we can compute the gradient ∇𝐶(𝑤 𝑡 )

because 𝐶 is differentiable,

• the opposite of this gradient gives the direction of steepest descent,

• at every iteration 𝑡 we take a small step towards that direction:

• if the steps are small enough, then ∀𝑖, 𝐶(𝑤 𝑡+1 ) < 𝐶(𝑤 𝑡 ), (A.15)

• if the steps are also large enough, then lim 𝑡→∞ 𝑤 𝑡 → 𝑤 * (optimization succeeds). (A.16)

Let 𝐶 : R 𝑑 → R be differentiable with the following general convexity properties:

• 𝐶 has a single minimum 𝑤 * .

• The opposite of the gradient points towards the minimum 𝑤 * :

• The gradient does not grow too fast when we move away from the minimum:

Let (𝛾 𝑡 ) 𝑡 be a sequence such that:

(step sizes allow traveling arbitrary distances in R 𝑑 )

If the update rule for (𝑤 𝑡 ) 𝑡 is:

A.5.2 Stochastic gradient descent (SGD)

There is, however, an issue when using gradient descent. Recall expression (A.8):

Differentiating that expression gives:

Computing this gradient has a complexity growing linearly with 𝑁 : this means that for large datasets the cost of computation can become prohibitively expensive.

204

Stochastic gradient descent deals with that issue. This variant is very similar to gradient descent but only uses an approximation of the true gradient to perform optimization. In practice, this consists of computing the gradient for only a few (𝐵) samples at a time then performing a gradient step at each iteration 𝑡. We define the following random variable, for 𝐵 ≥ 1:

Immediately we derive:

The resulting algorithm is similar to gradient descent, except that at every iteration i, we take a step towards a random direction 𝐻(𝑧, 𝑤 𝑡 ) that, on average, corresponds to the true gradient. Sampling that function is done by computing the gradient 𝜕𝐶 𝜕𝑤 only on a small subset of the dataset containing 𝐵 samples drawn randomly without replacement. A larger sample size 𝐵 leads to a better approximation of the gradient.

If 𝐵 = 𝑁 , we obtain the previous gradient descent algorithm.

The following theorem ensures that the algorithm converges almost surely.

Theorem 3 (Stochastic Gradient Descent convergence). This theorem is proposed in [START_REF] Bottou | Online algorithms and stochastic approximations[END_REF] and proves almost-sure convergence in a convex case.

Let 𝐶 : R 𝑑 → R be differentiable with the following general convexity properties:

• 𝐶 has a single minimum 𝑤 * ,

• the opposite of the gradient points towards the minimum 𝑤 * :

(A.27)

Let 𝑧 ∼ 𝑃 , where 𝑃 is a probability distribution. Let 𝐻(𝑧, 𝑤 𝑡 ) satisfy:

• 𝐻 is a stochastic approximation of the true gradient ∇ 𝑤 𝑓 :

satisfying predictions on new samples.

In Section A.4, we introduced continuous loss functions that approximate the empirical risk in a differentiable way, allowing the use of gradient descent methods on the parameters of the classifier functions for this optimization. This allows defining differentiable objective functions that notably contain regularization terms, sacrificing performance on the training set to obtain better generalization and reduce overfitting.

In Section A.5 we mentioned convergence theorems for gradient descent algorithms, and also introduced the very important stochastic gradient descent algorithm, which is the standard algorithm for training neural networks, along with its convergence properties and shortcomings in the non-convex case, notably the local extrema issue that makes training neural networks complicated.

The learning framework that we described in this Appendix builds on parameterized differentiable classifier functions; neural networks fit in this class as we will see in the second part of this technical background, in Appendix B.

Appendix B Technical background -Neural networks

Outline

In this second part, we focus on convolutional neural networks and describe their underlying principles. We saw in Appendix A that classification is a very important building block in computer vision that can be seen as an optimization problem on differentiable parameterized functions. The goal of this Appendix B is to show that neural networks are a particular restriction of the function set, that fits in the learning framework described in Appendix A. We first start with a short math preliminary, in Section B.1 to briefly discuss the dot-product.

Then, in Section B.2 we will describe architectures that define neural networks as parameterized functions and explain the elements that are necessary for executing backpropagation, which is an algorithm that computes gradient. We will see that neural networks are specific arrangements of modules called layers.

In Section B.3 we will describe some simple layers that are used in neural networks, notably the fully-connected layers and element-wise nonlinearities. In Section B.4 we will introduce tensors and pooling layers, that exploit their structure. In Section B.5 we will describe the important convolution layer which is the core element of convolutional neural networks. In particular we want to expose the heavy linear Let 𝐴 ∈ R 𝑑×𝑀 be a matrix such that 𝐴(., 𝑖) = 𝑎 𝑖 for all 𝑖 ≤ 𝑀 .

Let 𝐵 ∈ R 𝑑×𝑁 be a matrix such that 𝐵(., 𝑗) = 𝑏 𝑗 for all 𝑗 ≤ 𝑁 .

Let 𝐶 = 𝐴 𝑇 × 𝐵, where × is the matrix multiplication operation. We have 𝐶(𝑖, 𝑗) = (𝑎 𝑖 |𝑏 𝑗 ) for all 𝑖 ≤ 𝑀 and 𝑗 ≤ 𝑁 .

When we want to perform dot-products between many vectors (𝑎 𝑖 ) and many vectors (𝑏 𝑗 ), all computations can be done within a single matrix multiplication as shown in Figure B-2. It is important to spot matrix operations, because their implementations are extremely optimized in computers thanks to the Basic Linear Algebra Subprograms formalism (BLAS, Lawson et al. [1979]). This property is thoroughly used for efficiently computing the convolution layer that we describe later in Section B.5, and is a large component of the success of GPUs in neural networks. [START_REF] Matthew | Visualizing and understanding convolutional networks[END_REF],

Study of convolution filters by

the authors provide an insightful study of the role played by various filters in AlexNet, by studying what patterns in images activate filters the most in a convolutional network. We show their visualization in Figure B-24. We can observe that layers in the network activate against progressively more semantically meaningful patches, corresponding to larger receptive fields because of the stacked convolutions and poolings.

Rules for building an architecture. Unfortunately, there are no provably true rules for how an architecture should be designed for best performance. However, practice led to some heuristics on this difficult issue:

• There should be a nonlinearity layer after each weighted layer.

• Deeper networks (longer sequences of layers) are better.

Designing a good architecture is a long process of trial-and-error.

The balance of computation in layers. In an architecture such as AlexNet, processing a single image (forward) corresponds to 725 million floating-point operations (FLOPs). The architecture contains 60 million parameters. Convolution layers perform roughly 95% of the FLOPs and contain 5% of the parameters. The fully-connected layers perform 5% of the FLOPs and contain 95% of the parameters.

Max-pooling and nonlinearity account for less than 1% of the total number of operations. Therefore, faster implementations of the convolution layers are critical to the success of these algorithms, and improvements have appeared over time, with the GPU convolution of [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], the Fourier Transform based algorithm of [START_REF] Mathieu | Fast training of convolutional networks through ffts[END_REF], the Winograd algorithm of [START_REF] Lavin | Fast algorithms for convolutional neural networks[END_REF] and the optimized implementations by nVidia in cuDNN [START_REF] Chetlur | cudnn: Efficient primitives for deep learning[END_REF]).

Appendix C

Results of Evaluation of Generative

Adversarial Networks with Classifier

Two-Sample Tests

Architectures and filter parameters. We detail here the architectures of the generator and discriminator, that depend on the parameters gf and df.

DC-GAN generator architecture with parameter gf:

1.

Appendix D Toy experiment with distances

In this appendix, we build a controlled setup and observe the behavior of different distance measures on distributions that we compute numerically on a simple problem, in order to understand these distances better.

D.1 Experiment

Here we investigate the Kullback-Leibler Divergence (KL), Jensen-Shannon Divergence (JS) and Earth Mover Distance (EMD), defined in 5.5.1 in the main text. In order to understand better the differences and issues related to the distances, we design a simple data-fitting problem inspired by Independant Component Analysis (ICA, [START_REF] Hyvarinen | Independent component analysis[END_REF]) and observe the assumptions required as well as the results obtained with KL, JS and EMD.

We describe a simple case of ICA where we have access to samples (𝑢, 𝑣) = 𝑇 (𝑥, 𝑦),

where 𝑥 and 𝑦 are independent random variables following some distributions. The goal is to find 𝑇 -1 and thus retrieve the (𝑥, 𝑦) distribution. In our experiments, 𝑇 corresponds to a rotation transformation. ICA is useful, for example, for blind source separation.

Data and model

We describe the data and model that we use for this ICA-inspired experiment below. What we solve. In this ICA-inspired problem, the goal is to retrieve the rotation angle 𝜃 that corresponds to the best fit.

In order to use the KL and JS divergences that require density overlap, we use density estimation using a Parzen Window estimator as described above. To add this circular blob of noise, we do an important assumption: the 𝑥-and 𝑦-directions are equivalent in this problem, implicitly defining a metric over the 2D space through the addition of isotropic noise.

In the case of EMD, we do the same assumption but explicitly, and define the ground metric (the distance between pairs of samples) as the Euclidean distance over R 2 . We discuss this assumption after the experimental results.

D.2 Implementation details

Overlap-based metrics (KL and JS). For our experiments, we restrict ourselves to a low-dimensional setup, where we can compute KL and JS using numerical integration with Simpson's method (explained in Press et al. [1992]), as numerical The JS divergence is more tolerant and will drop some samples and shrink the rectangle, thus increasing its density (it sums to 1 in all cases). The tradeoff in JS consists of balancing the penalty for dropping a sample vs. the penalty for having a smaller density within the rectangle. This tradeoff defines an implicit regularization, and solutions with overlapping areas that have better density estimates are preferred, in contrast to KL which will attempt to create as much overlap as possible between the data and the model.

With EMD, there is now a notion of distance between points of the space, and overlap is not taken into account anymore: the penalty for ignoring samples is now proportional to the ground distance. Our experiments suggest that EMD captures the general shape of the data better (as the rotation angle 𝜃 for the rectangle model is closer to 0). This behavior is controlled by the ground distance function (here Euclidean), providing an additional parameter to control the solution that is found.

Our observations are similar to those of [START_REF] Theis | A note on the evaluation of generative models[END_REF] as they show different solutions obtained by optimizing different objectives.