Résumé

Les vidéos représentent des scènes complexes, comprenant des humains et des objets, illustrant les interactions entre ces derniers et leur environnement. Les relations entre agents sont susceptibles d'évoluer dans le temps et les agents peuvent effectuer des "actions". La compréhension automatique des vidéos nécessite de correctement localiser les agents à la fois dans l'espace et dans le temps. De plus, il faut décrire les relations entre ces agents et leur évolution temporelle.

La vision par ordinateur repose souvent sur l'apprentissage supervisé, où des échantillons étiquetés permettent d'apprendre les paramètres d'un modèle. Cependant, pour des données aussi riches que la vidéo, l'étiquetage est coûteux et compliqué. Les étiquettes symboliques ne sont pas suffisamment riches pour encoder les interactions entre personnes, objets et scènes. Le langage naturel offre une puissance descriptive qui en fait un modalité pratique pour annoter des données vidéo. Nous proposons de mettre l'accent sur la modélisation conjointe de vidéo et de texte. Nous explorons des modèles joints dans le contexte de films avec leurs scripts de tournage. Le principal défi auquel nous sommes confrontés est que les scripts de films ne fournissent pas de localisation spatiale et temporelle des objets et des actions.

Nous présentons d'abord un modèle permettant d'associer automatiquement des étiquettes de personne et d'action aux détections de personnes dans les films. Le modèle utilise une fonction de coût de clustering discriminatif, et une supervision faible sous la forme de contraintes que nous obtenons à partir de scripts. Cette approche nous permet de localiser spatialement et temporelement les agents et les actions qu'ils effectuent dans la vidéo, tel que décrit dans le script. Cependant, la localisation temporelle et spatiale est principalement due à l' utilisation de détections de personnes.

Nous décrivons ensuite un modèle permettant d'aligner des phrases avec les images de la vidéo. La correspondance temporelle est obtenue en utilisant un modèle discriminatif sous contraintes d'ordre temporel. Ce modèle d'alignement est appliqué à deux ensembles de données : un composé de vidéos associées à un flux d'étiquettes ; un autre composé de vidéos et descriptions sous la forme d'étapes). 5

Abstract

Videos often depict complex scenes including people, objects and interactions between these and the environment. Relations between agents are likely to evolve in time and agents can perform actions. The automatic understanding of video data is complicated as it requires to properly localize the agents both in space and time.

Moreover, one need to automatically describe the relations between agents and how these evolve in time.

Modern approaches to computer vision heavily rely on supervised learning, where annotated samples are provided to the algorithm to learn parametric models. However, for rich data such as video, the labelling process starts to be costly and complicated. Also, symbolic labels are not sufficient to encode the complex interactions between people, objects and scenes. Natural language offers much richer descriptive power and is thus a practical modality to annotated video data. Therefore, in this thesis we propose to focus on jointly modelling video and text. We explore such joint models in the context of movies with associated movie scripts, which provide accurate descriptions of the pictured events. The main challenge that we face is that movie scripts do not provide precise temporal and spatial localization of objects and actions.

We first present a model for automatically annotating person tracks in movies with person and action labels. The model uses a discriminative clustering cost function, and weak supervision in the form of constraints that we obtain from scripts. This approach allows us to spatially and temporally localize agents and the actions they perform, as described in the script, in the video. However, the temporal and spatial localization is due to the use of person detection tracks. Then, in a second contribution, we describe a model for aligning sentences with frames of the video. The optimal temporal correspondence is again obtained using a discriminative model under temporal ordering constraints. This alignment model is applied on two datasets: one composed of videos associated with a stream of symbolic labels; a second one composed of videos with textual descriptions in the form of key steps towards a goal (cooking recipes for instance).

Chapter 1 Introduction

Goal

The amount of visual digital data grows rapidly year by year. Much of this image and video data is generated by users and shared online. For example, Facebook users upload more than 350 million pictures every day and these numbers are very likely to grow. Facing such big amounts of data calls for algorithms capable of understanding and automatically sorting these huge data collections. There are many reasons for that, including the ability to make these collections searchable, abusive content detection, or efficient indexing. Nowadays things start to be even more complex as people also start sharing very large amounts of video data. Compared to images, video requires additional methods and resources for understanding dynamic scenes and events. Automatic video understanding is a complicated problem that leads to many interesting applications. Videos typically depict complex relationships between people and their environment that evolve in time. Understanding what is going on in a video implies recognizing the context (scenes), objects, people, how they interact and keeping track of all this information along the video. However, designing good models for these concepts requires some kind of common knowledge or annotated data. Indeed, modern approaches to visual recognition are based on supervised machine learning techniques, which in most cases require precisely annotated data. For instance to rec-Jane gets in the car. Lester hurries out the front door, carrying a BRIEFCASE.

Nothing takes the joy out of a road trip like a flat tire. Do you know how to change it? Williams arrows a good serve at T, Sharapova is unable to return it.

Figure 1-1 -Illustration of readily available video data with associated textual descriptions. These include from left to right: feature movies and associated scripts, YouTube videos and their descriptions, and sport video commentaries. ognize cats, these models are trained by presenting the algorithm with a set of images that picture a cat and other ones that do not. As we will discuss it later, completely annotating a video is very hard and it is not clear what kind of information should be annotated.

However, in many cases, video data comes with textual descriptions that can be meta-data, subtitles or scripts. Some examples of such paired video-text data are illustrated in Fig. 1-1. This data is highly correlated with the visual content of the video, event though there is no precise alignment between the two. For instance, if the subtitles mention a character named "James", it is the viewer who infers to which face it corresponds to. The viewer usually needs some time to actually recognize who is who, based on correlations between the dialogues and images.

The goal of this work is to develop models that enable us to work with videos that are associated with such textual data. We would like to build algorithms that use the two modalities and connect them in some ways. As most modern computer vision advances are based on supervised machine learning techniques, the simplest thing that one can imagine, is using textual data as a form of supervision. The first problem with this kind of approach is that such raw text cannot be directly used as annotations. It is often very noisy and imprecise, only partially describes the scene, and there is a high variability in the expressions. Moreover, this line of work leads to an asymmetric approach which can be criticized. Indeed, both text and video understanding can benefit from one each other and one of these modalities should not be used as a supervision for the other one. Also, as mentioned earlier, textual descriptions that are associated with videos are usually only coarsely aligned. The exact correspondence in time and space is not given a priori and we would like to build models capable of recovering this alignment.

We want our method to be able to exploit some textual and visual representation and align the two modalities based on data correlations. To this end we need to design a system that can discover these correlations while dealing with the uncertainty in the alignment.

This idea of aligning textual and visual information will be at the core of this work. Similar problems arise when working with images with captions, since the correspondence between nouns in the caption and objects in the image is unknown.

In video, however, the alignment must be found in space but also in time, depending on how precisely the textual description is located in time. This spatio-temporal alignment problem is illustrated in Fig. 1-2, for a scene description found in the movie Fargo. The script mentions character names and describes what they are doing but we don't know how they look, and what these actions look like. If one knows that Marge gropes in the dark while Norm keeps on sleeping, a single glance at the frame allows us to identify who is Norm and who is Marge. However, we have a precise idea of what a sleeping person looks like while this is not so obvious for an algorithm.

The better a textual source is aligned, the simpler the association task would be.

For instance, movie subtitles are precisely aligned in order to match the speaker's lip movements, which makes character identification simple. On the other hand, a YouTube video description is much more imprecise, and potentially describes a long piece of video (several minutes). Moreover, the alignment can be carried out at different scales, either on the level of words or entire sentences, parts of images or whole video frames. In the work described in this thesis, we explore spatial and temporal alignments, both at the level of words and sentences.

The bedroom is dark. Norm is snoring. The phone rings. Marge gropes in the dark. Marge props herself up next to the still-sleeping Norm.

Figure 1-2 -Illustration of a video frame along with the corresponding scene description found in the movie script. The movie script precisely describes what is happening in the video but no correspondence to regions in the image are given. The goal of joint video-text models would be to answer the following questions: Who is Norm? Who is Marge? What does a phone look like? How does one grope something? What does it look like to prop oneself up?

Motivation

The line of work presented in this thesis is motivated by several observations. The first one is the fact that the kind of data we want to exploit is often freely available and its quantity will keep on growing. Movies are often provided with subtitles and shooting scripts. More and more television platforms propose movies with Descriptive Video Service (DVS) descriptions for the visually impaired. These descriptions provide a precise audio description of what appears on the screen. Even though they are in the form of speech signal, these can be automatically transcribed into text. Sport events are usually provided with a commentary describing the action happening on the field. It precisely relates players actions and gives a higher level interpretation of the players behavior, for example whether or not specific actions led to the victory.

Recently, it has become quite popular to post on-line "how-to" videos, providing step by step guides for a given task. These are usually associated with text or voiceover describing each step (as a description of the video). All these correspond to a rich source of information, describing the key elements of the video. Most importantly, this kind of information was not generated on purpose for a computer vision experiment. Therefore, it is not biased towards potential computer vision applications and describes the content that really matters to the observer. Also, in most cases, it has been written (or spoken) by an expert in the field, trying to best describe the relevant events. This kind of data should be seen as much richer, more complete and faithful to the video stream than crowd-sourced descriptions. Video descriptions obtained on platforms such as Amazon Mechanical Turk are written by people who received precise orders and that are usually paid by the sentence they write. Moreover, such textual descriptions describe the video at different levels of detail and target very different tasks. This provides precise expert knowledge for very fine-grained action recognition. For instance "how-to" videos allow to learn models for very specific tasks, for which it would be very painful and time consuming to hire annotators.

Most recent advances in computer vision are due to fully-supervised machine learning techniques. These correspond to learning algorithms that are capable of building a model of an action (for instance "Standing Up") provided they are shown examples of this action. A typical learning scenario for action recognition would involve hav-Figure 1-4 -Three frames from a scene in the movie Moonstruck that picture Loretta and Cosmo having champagne. The action "eat" as defined in standard action recognition dataset also include drinking. However, how is the "eating" action really defined? Are the temporal borders really clear? Does it start when one pours the drink into a glass (frame 1)? Does it correspond to holding the drink in hand (frame 2) or is it really the fact of pouring the drink in his mouth that matters (frame 3)?

ing a set of examples (videos) associated with a label. The label would be telling us whether or not the given video pictures the action of interest. We show in Fig. 123several examples from a fully-supervised action recognition dataset [START_REF] Marszalek | Actions in context[END_REF]. The second observation that motivates this work is that manually defining such labels for video understanding is very hard. Indeed, scenes shown on video are very complex, usually portraying the interaction between multiple agents and objects, and go far beyond a single concept.

In the last decade, a substantial amount of research in video understanding has been dedicated to human action recognition. However, the definition of "action recognition" is still fuzzy, and providing a proper description of an action is a problem in itself. This is not only a problem faced in computer vision, and corresponds to a whole branch of philosophy. Most recent computer vision advances in the field define an action by a symbolic label that is shared by several videos. For example, in the context of sports video classification, labels correspond to what sport is practiced:

Hockey, Soccer, Tennis etc... In the context of simpler, every day actions, the definitions are much more fuzzy. In previous work, given a fixed vocabulary of actions, the precise definition of an action is usually annotator dependent. All annotators will not have the same idea as to how an action looks like: for instance, is opening a fridge door an instance of the class "Open Door"? Also, people may often disagree on the temporal extent of the action: when does "drinking" start, and when does it end? We illustrate how hard it is sometimes to properly set the temporal bounds of an action in Fig. 1234. In our work, we propose to avoid defining action classes manually and exploit readily available data instead.

This work is also motivated by the fact that manual annotation of video data is highly tedious. This is due to many reasons, the first of them, being the lack of precise definition of what an event or action is. Therefore, annotating actions in movies requires the annotator to take many decisions, some of which can be quite arbitrary.

Unlike objects, which have a precise spatio-temporal localization, an action's borders are much more fuzzy. Annotating a whole movie with action labels implies watching the movie a few times and setting start and end markers for every observed instance. This is a very time consuming process that requires a lot of attention and patience, and we believe that automated alignment can greatly lighten the annotation work.

This way, the annotator would only provide rough localization, and the developed methods could take this imprecision into account and still come up with good models. Moreover, actually finding instances of a given action is hard because of their infrequent occurrence. For instance, on a set of 69 Hollywood movies, "answering a phone" happens on average 3.2 times per movie while "shaking hands" only happens 2.0 times.

Eventually, this line of work also allows us to move away from the traditional clip classification paradigm. Indeed, most work on action recognition and video understanding takes as input trimmed video clips that illustrate a specific action. This trimming, which is usually part of the annotation introduces a bias which is not present in freely available data (such as private video collections, TV, movies etc.).

We propose to exploit boundaries as provided by a rough alignment of textual data, and refine this alignment if needed.

Based on the motivations described in this section, we want to design models that could use readily available meta data as a source of supervision. As explained before, such data offers information about a large set of tasks, for instance in the context of "how-to" videos. However, using it to learn models is complicated because this supervisory information is often imprecise, not localized in space nor time. Therefore

As the headwaiter takes them to a table they pass by the piano, and the woman looks at Sam. Sam, with a conscious effort, keeps his eyes on the keyboard as they go past. He appears to know this woman. After she has gone by Sam steals a look in her direction. BERGER, a slight, middle-aged man, observes the couple from a distance. The headwaiter seats Ilsa. Laszlo takes the chair opposite and surveys the room. Strasser and Renault look up at them from their table.

Figure 1-5 -Temporal alignment problem illustrated using a scene from Casablanca.

The scene description as found in the movie script is shown above. We manually picked the corresponding frames and used a color code to align parts of sentences to them. This shows that even though the description from the script is rich in details, it is very imprecisely localized.

we need to be able to deal with noise and uncertainty in this very weak form of annotations. We will describe what are the main challenges related to our goal in the following section.

Challenges

We will try to sketch out the main challenges related to our goal. These are related to the encountered machine learning problems as well as to how the data should be represented. We discuss these two in detail below.

The main challenge addressed in this work is the lack of precise correspondence between the two streams of data (video and text). As mentioned before, one of the aims of this thesis was to design joint text and video models. However, such models are usually trained using pairs of data points in correspondence. As illustrated in Fig. 1-5, when using movies with roughly aligned scripts, this correspondence is not given a priori. We only know that parts of the video data are related to parts of the textual description. In the figure, a long block of text is roughly aligned to a long video sequence. Even though all events described in the text do happen in the video, we don't know precisely when and where in the scene. We illustrate the correspondence that we would like to recover using a color scheme. As we will describe it more formally in the next chapter, we will refer to this kind of scenario as weakly-supervised learning.

This concept is at the core of this thesis and is one of the main challenges that we faced while working with this kind of data.

The second challenge is related to the data representations that we have to use.

The goal, as described above, would require a high-level video understanding, going further than simple classes or labels. Indeed, the represented scenes can only be understood by recognizing the agents, their relations and how they interact. It is not clear what would be a suitable representation to generate such high level interpretations. How should we represent the video? How should we represent the textual description? Should we embed both modalities to a common space? Should we use some kind of symbolic representation? This is an open problem both from the computer vision and the natural language understanding perspectives. Building symbolic representations from natural language is hard and would again provide a discrepancy between video and text. On the other hand, continuous text representations such as word2vec [START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF] or sentence embeddings discard the complex underlying structure.

Contributions and outline

This manuscript is organized into seven chapters, including this introduction. In Chapter 2 we present an overview of previously published work that is related to our goal and to the proposed models. After this review of the relevant literature, we provide in Chapter 3 a brief overview of models and methods used in our work. This will allow us to precisely define the terminology used in subsequent chapters.

Chapter 4 describes the first contribution, a model for jointly identifying the actors and actions they perform in movies. We propose to process textual descriptions and extract <PERSON, ACTION> pairs that we will use as a form of weak supervision.

The idea is that character identities act as a strong cue to localize the action, allowing us to learn a model on the level of characters and not the whole frame. We learn a model for every character and models for actions using a discriminative clustering criterion [START_REF] Bach | Diffrac: a discriminative and flexible framework for clustering[END_REF] and constraints that we derive from the aforementioned supervision. Using a simple convex relaxation, the cost function is optimized by solving a sequence of convex quadratic programs. We show experiments conducted on two feature movies: Casablanca and American Beauty. The developed model allowed to cope with uncertainty and imprecision in the data and outperformed the state-of-the-art algorithms at that time. This work was presented at ICCV 2013.

In Chapter 5, we describe the second contribution, a model for aligning sentences to video frames. Given the two streams, one composed of sentences and the other one of video frames, we want to find the temporal correspondence between the two. We do this under the assumption that the temporal ordering is maintained. As in the first contribution, we do so by using a discriminative clustering criterion and a structured optimization domain. We take advantage of the structure of the underlying space and optimize our cost function using the Frank-Wolfe algorithm [START_REF] Frank | An algorithm for quadratic programming[END_REF].

The model is evaluated on two datasets: one composed of videos with sequences of labels, the other one composed of cooking videos along with textual descriptions in the form of steps. This work corresponds to publications presented at ECCV 2014 and ICCV 2015.

Finally, we conclude and discuss potential future work in Chapter 6.

Chapter 2

Related Work

In this section we review work that is closely related to this thesis. We first discuss previous methods for modeling text and images. This includes image captioning, image retrieval based on textual queries, and weakly-supervised methods using text to supervise visual models. Next, we describe approaches using textual descriptions of video data, and discuss some works on modeling the temporal aspect of videos. We conclude the chapter by a brief overview of the literature related to the models and optimization techniques that we will present in this thesis: discriminative clustering and the Frank-Wolfe optimization algorithm.

Images and text

Image captioning

During the last decade much work has been dedicated to the joint modeling of images and their textual descriptions. The ultimate goal is to represent both types of media in a shared space where their relations can be modeled and analyzed. Many approaches have been proposed and we describe some of them here.

Captioning as machine translation. One of the early attempts towards modeling images and text was presented in [START_REF] Duygulu | Object recognition as machine translation: Learning a lexicon for a fixed image vocabulary[END_REF]. The idea was to use a machine translation model to align parts of images to words from image captions. The authors propose to decompose images into regions and to represent each region by an entry in a dictionary. Given symbolic representations for words and image regions, the alignment was phrased as an IBM 2 model [START_REF] Peter | A statistical approach to machine translation[END_REF]. This model contains two distributions: the probability of an image region given a word and the probability of aligning a word to a given image region. As in the classical translation model, the optimal assignment is recovered using an expectation maximization (EM) algorithm.

A broader set of such translation-inspired models is presented in [START_REF] Barnard | Matching Words and Pictures[END_REF]. In addition to the aforementioned IBM model, the authors describe a multimodal extension of latent dirichlet allocation (LDA) and an extension of a hierarchical clustering model, using text and visual appearance.

The work of [START_REF] Duygulu | Object recognition as machine translation: Learning a lexicon for a fixed image vocabulary[END_REF] was extended a few years later in [START_REF] Gupta | Beyond Nouns: Exploiting Prepositions and Comparative Adjectives for Learning Visual Classifiers[END_REF] taking into account relationships between nouns. The previously used dataset is extended so as to contain not only a set of nouns for each image but also the spatial relations between them. A more complex probabilistic model that includes relationships between pairs of nouns is introduced and optimized using the EM algorithm. Quantitative results are shown on the extended dataset, and demonstrate significant improvements in image labeling performance for image labeling.

Fixed templates. Another line of work proposes to match images and sentences in a common semantic space. [START_REF] Farhadi | Every Picture Tells a Story: Generating Sentences from Images[END_REF] consider a semantic space composed of fixed template: a triplet of labels of the form <o,a,s> (object, action and scene).

They model these triplets as a conditional random field (CRF) with unary potentials defined as functions of object detectors (for images) or words. The CRF is trained using a dataset composed of images with an associated textual description and a ground truth <o,a,s> triplet. In the experimental section, authors show that the common semantic representation can be used to annotate images by picking sentences that correspond to the same inferred triplet.

The template representation is further extended by [START_REF] Kulkarni | Baby talk: Understanding and generating simple image descriptions[END_REF]. Instead of including a single <o,a,s> triplet per image, the authors propose to create a node per object detection. Each detection is further associated with an attribute node, and each pair of objects is associated with a preposition node. Unary potentials for this model come from standard object detectors, attribute and prepositional classifiers.

The pairwise features are computed on a held-out set of data. Once the CRF has been trained, for a given test image one can perform inference and obtain the most likely pattern. The authors propose to generate captions using the words from this pattern and filling in "function words" using a language model. That way, a template <<white,cloud>,in,<blue,sky>> would be transformed into "There is a white cloud in the blue sky".

Retrieval and CCA. Much of the work on joint representations of text and images makes use of canonical correlation analysis (CCA) [START_REF] Hotelling | Relations between two sets of variates[END_REF]. CCA consists in finding linear transformations of two variables such that their correlation is maximized. Performing CCA on two modalities finds two projections that allow to bring the two data sources into a common space. This has been explored for images and text by [START_REF] Hardoon | Canonical correlation analysis: An overview with application to learning methods[END_REF], who propose to use a kernelized version of CCA. Sentences are described using term frequencies and standard visual features are computed on images. After learning the two projections, the authors propose to retrieve the closest image given a textual description. [START_REF] Ordonez | Im2text: Describing images using 1 million captioned photographs[END_REF] propose to return the caption of an image that is most similar to the query image. The proposed model does not use CCA but relies on the construction of a very large captioned image database. Given a query image, a set of similar images in the database is found based on scene features, such as GIST, of heavily sub-sampled thumbnails. The set of retrieved images is re ranked based on various scores, based on object detections, attributes, people and scene features. The caption of the highest ranked image is returned as a result.

CCA-based image captioning methods are discussed in general by [START_REF] Hodosh | Framing image description as a ranking task: Data, models and evaluation metrics[END_REF]. The authors introduce a large benchmark dataset and compare different variants of the model, using various feature representations. Also, the evaluation metrics for image captioning are discussed, and are compared to human judgment. The top-ics discussed in this paper are particularly interesting given how hard this task is to evaluate.

Extensions to the kernel CCA-based models are proposed in [Gong et al., 2014a,b]. Gong et al. [2014a] propose a multi-view variant where the CCA is computed between three modalities. In that work, the modalities include images, tags that one can typically find in meta data on the web, and image classes. The empirical evaluation includes experiments on several datasets with various retrieval schemes: from tag to image, from image to tag. Gong et al. [2014b] propose to help the image-text embedding using a large but weakly annotated set of images. The main dataset is Flickr30K, where each image is associated with a precise description in natural language. This work investigates whether using the much larger but imprecise Flickr1M and SBU1M datasets can enhance the quality of the embeddings. Indeed, images from these datasets contain titles, tags and very imprecise textual descriptions. The authors demonstrate empirically a moderate improvement in performance when additional data is used.

Not directly related to image captioning (with complete sentences), but also formulated as a retrieval problem, [START_REF] Weston | Wsabie: Scaling up to large vocabulary image annotation[END_REF] propose to learn a model for annotation retrieval given a query image. Images are annotated by a single tag, but the datasets used to train the model are "web scale": they contain 10M training images. The model is trained using a ranking loss, learning an embedding of visual features and annotations such that the correct label is ranked as high as possible.

The embeddings learnt that way for the annotations exhibit some semantic information, as nearest neighbor queries amongst annotation embeddings show interesting similarities.

Deep models. Recently, there has also been an important amount of work on joint models for images and text using neural networks. Many caption generation (or retrieval) variants have been proposed in 2014 and 2015 some of which we will describe here. A significant part of these still rely on a ranking loss and formulate captioning as retrieval, but some propose to learn a caption generation model. Image captioning can either be evaluated by a retrieval metric or by comparing the single proposed caption with the ground-truth one. The advantages of the two approaches are discussed in [START_REF] Hodosh | Framing image description as a ranking task: Data, models and evaluation metrics[END_REF], with an indication that the ranking measures provided more reliable numbers. We will now describe in detail some of the proposed deep captioning models.

Closely related to [START_REF] Weston | Wsabie: Scaling up to large vocabulary image annotation[END_REF], the work of [START_REF] Frome | Devise: A deep visual-semantic embedding model[END_REF] introduces a ranking-based image annotation model. It has the advantage of considering non linear transformations of the image representation and being able to generalize to annotations that have never been seen in the training set. Annotation embeddings are initialized using word2vec representations [START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF], and images are represented using a deep convolutional neural network. The similarity between annotations and images is measured using a trainable bilinear form 𝑀 . At first, only the bilinear form 𝑀 is optimized, while in the second step of the optimization, the loss is also propagated to the image representation.

While the previously described work computes embeddings for single words of phrases, similar models have been developed for whole sentences [START_REF] Socher | Grounded compositional semantics for finding and describing images with sentences[END_REF].

In this article, the authors propose to compute a sentence representation and use a ranking loss between images and sentences. A global image representation is used and the sentence is described using a dependency tree recurrent neural network (DT-RNN). In a classical RNN, the nodes of the network correspond to words that are connected as a chain. In this work, the authors propose to create one node per word and connect them following an automatically computed dependency tree. The sentence representation is computed at the root. As for other works, the whole model is trained using a ranking loss and compared to previous work, including CCA-based models.

The previously described model measured the similarity between a global image representation and a whole sentence. Another ranking-based model has been proposed

in [Karpathy et al., 2014], where fragments of an image (object detections) are aligned to fragments of a sentence (dependency relations). The similarity between the image and a given sentence is measured using a latent alignment cost. All parameters of the model, including the alignment and fragment embeddings are trained as before using a ranking loss. The great advantage of this model is that the alignment was modeled explicitly which allows interesting interpretations. This model is extended and simplified in [Karpathy and Fei-Fei, 2014], where sentence fragments correspond to words. Words are embedded using a bidirectional recurrent neural network, which allows at test time not only to retrieve the closest caption but to actually generate one.

A very simple method, using global image representations and capable of generating new captions is proposed in [START_REF] Vinyals | Show and tell: A neural image caption generator[END_REF]. The work described in the previous section makes use of object detections and tries to resolve the alignment of words to parts of the image. In this article, a global image representation obtained from a very large CNN is fed as the first input of a recurrent neural network for text generation. The RNN takes as first input a linear transformation of the image representation and then subsequently the successive words of the ground-truth caption.

At test time, a novel sentence can be sampled by feeding the output of the image representation and then performing a beam search on the RNN outputs. The proposed model provides good performance while only having access to a global representation of images. Authors evaluate this approach using the BLEU score, but also report some ranking experiments. Captions of the training set are ranked by assigning them a probability given the query image. While the ranking results are encouraging, the authors argue that ranking is not the correct way to evaluate image captioning, hence, opposing the conclusions of [START_REF] Hodosh | Framing image description as a ranking task: Data, models and evaluation metrics[END_REF].

An alternative, phrase-based approach has been proposed by [START_REF] Lebret | Phrase-based image captioning[END_REF].

Phrases are defined as a group of words that express a specific idea, and are here classified into noun phrases, prepositional phrases and verb phrases. The authors propose to learn a joint model of images and phrases using a maximum likelihood criterion. The model assumes that the conditional probabilities of phrases from the same sentence, conditioned on the image, are independent. Then, the conditional probability of a given phrase is defined using a soft max of a bilinear product between a phrase embedding and an image representation. Images are represented using the output of a CNN while phrases are represented by the average of precomputed word embeddings. After optimizing the negative log-likelihood, at test time, a caption is generated by fitting a language model to the most likely phrases. The last re-ranking step, exploiting visual information, is used to choose the closest sentence. Please note that this method is generating novel captions and does not make use of a ranking loss.

Image captioning and text/image retrieval is a very interesting area of research that is currently lacking a proper task definition and suitable evaluation metrics. In the following section we will discuss how text and image captions can be used as weak supervision, for instance for face recognition.

Text as supervision

Textual information has extensively been used as a form of weak supervision to train visual models. This has especially been exploited in the context of person recognition in news photos. Indeed, news pictures are usually associated with captions which potentially describes the people pictured in the image. [START_REF] Berg | Names and Faces in the News[END_REF] were among the first to cope with this rich, free, yet imprecise data. The authors propose to detect faces and rectify them based on facial landmark locations to match a canonical pose. Pixel values of the image are used as features and are projected to a lower dimensional space using kernel principal component analysis (kPCA). Using images with unambiguous labels (portraits with a single name) the authors propose to perform linear discriminant analysis. In this lower dimensional space, a modified k-means clustering procedure is carried out to obtain face clusters associated with names. This work has been extended to a probabilistic formulation in [START_REF] Berg | Who's in the picture[END_REF], using a generative model of faces. The authors have also proposed to model how likely a name is to appear in the picture, conditioned on textual context information. The proposed model is optimized using expectation maximization and provides better results as compared to [START_REF] Berg | Names and Faces in the News[END_REF].

Related to the work described above, [START_REF] Luo | Who's doing what: Joint modeling of names and verbs for simultaneous face and pose annotation[END_REF] propose to extend person identification to action recognition. The goal is now not only to recognize celebrities, but also what they are doing. This article has relations to the previously described work on modeling relations between objects in images and text [START_REF] Gupta | Beyond Nouns: Exploiting Prepositions and Comparative Adjectives for Learning Visual Classifiers[END_REF]. In a similar spirit, the authors proposed a complete probabilistic model of person identities and related actions. The parameters of the appearance model and the text to image assignments are obtained using the EM algorithm. Empirical evaluation shows that modeling identities and actions jointly works better that only modeling identities. This work is quite similar in spirit to what we will present in Chapter 4. [START_REF] Wang | A discriminative latent model of image region and object tag correspondence[END_REF] consider a model that allows to classify objects in images using latent attributes. The model does not take natural language as input but works on a "structured" label set, and makes use of richer labels. The model is cast in the

Video and text

Text has also been extensively used with video data. First, movie scripts provide a rich source of annotations for action recognition and person identification in movies.

This kind of supervision is weak as it does not provide precise sample-label correspondences. Several models have been proposed to cope with this kind of uncertainty, often yielding good models with only light supervisory burden. Following the attempts at image captioning, many approaches have been proposed for video captioning. These rely on well annotated video corpora, some of which we will describe here. The closest to our work are methods focusing on the task of aligning videos with corresponding textual descriptions. Some of these methods will be described below.

Weak supervision

Similar to the work on captions and faces in news, subtitles and movie scripts have been used together with the video signal to train action and character models. Movie scripts provide a precise description of what is happening on screen. Just like the movie, they are divided into scenes, specifying the setting that will take place. They include two kinds of textual information: dialogues and scene descriptions. Dialogues contain the name of the character that is speaking as well as the pronounced words. In between these dialogues, the script contains scene descriptions which describe how the characters behave and the enviornment in which they evolve. These scripts however do not contain any precise timing indications and are therefore unaligned with the actual movie. Most of them are shooting scripts, written before the shooting, and the final movie can differ (because of actor's performance, editing etc.).

Thanks to the expansion of collaborative subtitle sharing, textual transcripts of the monologues are freely available on the web. These precisely temporally aligned transcriptions provide a reliable description of the character's words. One can match the text found in the subtitles with dialogues from the scripts in order to roughly align the script in time. Exploiting this data as a form of supervision was first proposed in [START_REF] Everingham | Hello! My name is... Buffy" -Automatic Naming of Characters in TV Video[END_REF] and gave rise to many subsequent models. We will describe some of the most important ones here.

Face recognition. [START_REF] Everingham | Hello! My name is... Buffy" -Automatic Naming of Characters in TV Video[END_REF] propose to link subtitles to scripts in order to recover the identities of the speakers. Time-stamped subtitles with speaker identities can be then used as reliable labels to recognize people. In this early work, frontal faces are detected and tracked. Then facial landmarks are localized and described using either SIFT or raw pixel values. The link between subtitles and video is made by detecting lip motion to decide which character is speaking at that given moment. Using conservative thresholds, a reliable set of face tracks is assigned the correct character identity. The other tracks in the video are assigned to an identity using a simple probabilistic model.

This work is further extended in [START_REF] Sivic | Who are you?" -Learning person specific classifiers from video[END_REF] by introducing several improvements. First of all, a profile face detector is added, improving the face detection coverage. Better face descriptors are used, and a model is learned using a kernel SVM instead of simply relying on a distance in the feature space. The kernel is a mixture of different kernels, one per facial landmark, and between landmarks the closest descriptors in both tracks is used to compute the kernel entry. The weights of the mixture are learned and the whole pipeline provides much better performance. However, the use of textual information is identical to the previous work, and relies on heuristic matching of monologue speakers to lip motion.

An interesting alternative is proposed by [START_REF] Cour | Learning from ambiguously labeled images[END_REF]. Instead of relying on the explicit modeling of speakers to assign labels to face tracks, the authors propose to formulate the problem as an ambiguously labeled one. In the proposed model a data sample can be assigned to multiple labels, as subtitles often correspond to a dialogue.

The authors propose a loss that is suitable for this kind of ambiguous setting together with a convex surrogate that leads to a tractable learning algorithm. The method is evaluated on images with captions and on the TV series "Lost". This way of handling ambiguous script information in [START_REF] Cour | Learning from ambiguously labeled images[END_REF] is related to our contribution described in Chapter 4.

A method very similar in spirit to the contribution described in Chapter 4 is presented in [START_REF] Vignesh Ramanathan | Linking people in videos with "their" names using coreference resolution[END_REF]. While building upon our weakly-supervised character recognition model, the authors add interesting extensions. This work not only uses character mentions in the script to generate constraints, but also includes a model for co-reference resolution in the text. Indeed, characters are not always named using their full name and the joint text-and-video model allows to both improve face recognition and the co-reference. The authors demonstrate experimentally that both problems actually benefit from this joint model and evaluate this improvement along the iterations of the algorithm.

The work that we describe here only use scripts to recognize characters. In our work, we also investigate scripts as a source of supervision for training action models.

In the following section we will review some related publications that used movies and script data as a source of supervision of some sort.

Action recognition. Movies with associated scripts were first used in [START_REF] Laptev | Learning realistic human actions from movies[END_REF] to automatically build an action recognition dataset. The authors propose to train a text classifier that predicts whether the script mentions an action or not.

Eight different actions are considered and the classifier is trained on an annotated set of 12 movie scripts. Retrieving relevant scene descriptions using this classifier works much better than when using simple regular expression matching. The video corresponding to the classified scene description is used as training samples for learning an action classifier. Using the raw piece of video is compared with using a cleaned-up version where the temporal boundaries have been corrected by an annotator.

This work is extended in [START_REF] Marszalek | Actions in context[END_REF], adding several actions and better exploiting textual data. Apart from learning action models, this paper shows how to train scene classifiers using script-based supervision and evaluates both. A richer model of actions given a scene context is proposed where the influence of scenes on actions is either obtained from scripts (by counting) or trained. The action recognition dataset obtained in this paper constitutes the Hollywood2 dataset, which is a wellknown action recognition benchmark.

The previously described methods provide accurately labeled video clips but the temporal bounds are often imprecise. [START_REF] Duchenne | Automatic annotation of human actions in video[END_REF] address this problem by trying to automatically adjust these bounds based on a discriminative cost. Given the imprecise temporal bounds (extended by a given amount), the model selects the temporal window inside that is most discriminative. The problem is formulated as a discriminative clustering, based on the hinge loss. The optimization is carried out by a coordinate descent approach, iterating between learning the optimal model and picking the most discriminative window. This cleanup process is evaluated for the end task of action detection in movies for two classes of interest. The authors show that the cleaned-up windows provide better training samples than the raw ones but still worse than the ground-truth ones. This work is related to what we will describe in Chapter 5, where a list of actions is aligned to a video sequence.

Datasets

Several datasets with video descriptions have been released and used for building joint video and text models. In this section, we describe those that contain curated textual descriptions, written on purpose or manually corrected in some way. [START_REF] Regneri | Grounding action descriptions in videos[END_REF] present a video dataset designed to work on grounding textual descriptions. The point is to discover the "meaning" of sentences by looking at the corresponding visual data. The main contribution of this paper is the dataset, composed of 212 HD videos, each described by 20 different annotators. The videos correspond to a restricted cooking setup, where simple recipes are prepared in front of a static camera.

All videos come from a larger cooking dataset that is described in details in [Rohrbach et al., 2012a]. Descriptions are obtained using Amazon Mechanical Turk. Annotators were asked to describe the content of the video in 5 to 15 steps, each step being one sentence. Additional annotations were then added to measure the similarity between descriptions. Overall the dataset is interesting but of limited size, if one wants to train language models on it.

Another dataset of videos with associated textual descriptions was introduced in [START_REF] Rohrbach | A dataset for movie description[END_REF]. The dataset is composed of 94 movies, out of which 55 are provided with Audio Descriptions and 50 with movie scripts. A total of 11 movies are provided with both the audio description and the script which allows the authors to compare the quality of the two kinds of textual descriptions. Scripts are obtained from the web, aligned using subtitles as explained earlier, and then the alignment is corrected manually. Audio descriptions are descriptions that are provided for the visually impaired and describe precisely what is happening on screen. The authors propose to transcribe them to text using a crowd-sourcing audio transcription service.

The dataset is composed of 68337 video clips with a textual description, yielding in total 74 hours of video with more than 650k words. This dataset is much larger and contains very challenging visual content as compared to the restricted cooking setup. Some of the works described in the following section make use of the datasets that we have presented here.

Captioning

Another important line of work, fostered by the development of the datasets mentioned above, is automatic video captioning. Following the successes of image captioning, many variants of captioning models have been proposed. They all rely on the same key idea which is related to machine translation models. The video signal is encoded in some way into a latent representation, which in turn is transformed into a natural language sentence. In this section we describe some recent publications that propose such models.

One of the first attempts at automatic video captioning was proposed in [START_REF] Rohrbach | Translating video content to natural language descriptions[END_REF]. In the spirit of [START_REF] Farhadi | Every Picture Tells a Story: Generating Sentences from Images[END_REF], based on video features, a CRF is trained for a 5-tuple of classes: activity, tool, object, source, target. Using this fixed template representation, a translation model is trained to generate sentences. The parameters are optimized on the dataset presented in [START_REF] Regneri | Grounding action descriptions in videos[END_REF] and the performance is evaluated using the BLEU score. During training, because of the way the dataset is made, a single sentence can be assigned to multiple templates. The authors explore different ways to merge or select the relevant template for training. [START_REF] Donahue | Long-term recurrent convolutional networks for visual recognition and description[END_REF] propose to generate video captions using a long short-term memory network-based (LSTM) language model. Two other applications are also shown in this paper, including video activity recognition and image captioning but let us focus on the video description model here. The same CRF as described in the previous paragraph is trained on the video signal. The output of the CRF is then fed to the LSTM, which is trained to output the actual video descriptions. Three different strategies of feeding the CRF output to the LSTM are studied in the article.

The authors tried using the most likely 5-tuple as an input to and encoder-decoder LSTM, or using the output of the CRF as a constant input to a simple decoder model.

A very similar model is then presented in [Venugopalan et al., 2015b]. Instead of using a fixed template representation, a global video representation is used as a constant input to an LSTM decoder. The global representation is obtained by taking the average activation of a CNN along the frames of the video. This can be seen as simplification of the previously described model, where no intermediate CRF representation is used. Also, the authors evaluate their model on a different video dataset.

A third variant of this model is introduced in [Venugopalan et al., 2015a]. In a fashion similar to [START_REF] Donahue | Long-term recurrent convolutional networks for visual recognition and description[END_REF], the authors propose an encoder-decoder approach. However, instead of taking as input the 5-tuple, the decoder directly takes as input the sequence of CNN outputs on frames. As compared to [Venugopalan et al., 2015b], no average operation is performed over time, keeping the dynamic aspect of the video. The three works are different variants of the same model, always generating a sentence using an LSTM, with different ways of feeding the video as an input.

In a concurrent work, [START_REF] Yao | Describing videos by exploiting temporal structure[END_REF] describe an encoder-decoder video captioning model with an attention model. The decoder LSTM is conditioned on a visual feature 𝜑 𝑡 (𝑉 ) which is computed for every position 𝑡 in the output sentence. This feature uses an attention mechanism which weighs the frames of the video based on previously generated words and features of the given frame. This approach experimentally outperforms the method described in [Venugopalan et al., 2015b], showing the usefulness of the attention mechanism.

All these works produce natural language captions for videos which are inherently hard to evaluate quantitatively. The same problems as the ones discussed in the context of image captioning arise and still remain unanswered. In the following section we will describe models that instead focus on the problem of aligning videos with textual descriptions of some kind.

Alignment

Most related to our work, some previous methods focus on the alignment of textual data with video. The methodology described in [START_REF] Everingham | Hello! My name is... Buffy" -Automatic Naming of Characters in TV Video[END_REF] allows to align whole movie scripts with the associated video data. However, it makes use of subtitles which are redundant with the dialogues in the script and have precise temporal boundaries. [START_REF] Sankar | Subtitle-free movie to script alignment[END_REF] discuss a model for aligning a script with a movie when no such subtitles are available. The alignment then needs to rely on visual data, in order to match descriptions in the script to shots in the movie. The authors propose to find the optimal alignment using a criterion composed of three terms: One based on the scene location, another one based on character recognition and one on automatic speech transcription. The problem is solved using dynamic programming and evaluated provided ground-truth script to video alignment. The components of this method rely on several heuristics, which make strong assumptions on the structure of the movie (or show). An interesting application is shown, where scripts from silent films are aligned to the video.

More recently, [START_REF] Tapaswi | Book2movie: Aligning video scenes with book chapters[END_REF] propose to align books to their movie (or TV show) adaptations. The alignment is carried out at the level of chapters for books and scenes in the movie. Scenes in the movie are found using the method described in [START_REF] Sankar | Subtitle-free movie to script alignment[END_REF], while the segmentations into chapters is straightforward.

Similarity between scenes and chapters is based on textual features like character occurrences and dialogue matching. The whole optimization is framed as a shortest path problem in a properly defined graph. Aside from text-based features, the article describes two priors that encourage a linear alignment (it is costly to jump forward and backward in time). However, visual information is only used to segment the movie into scenes and to generate the list of characters that appear in a scene.

A related and contemporary work [START_REF] Zhu | Aligning books and movies: Towards story-like visual explanations by watching movies and reading books[END_REF] proposes to align books to their movie adaptation on the level of sentences and shots. The main difference with the previous work is that this alignment is recovered using visual information. The authors propose to learn a bilinear form between the video and sentence representations using a ranking loss. They use sentence representations pre-trained of a very large book dataset, using a model they published at the same time in [START_REF] Kiros | Skip-thought vectors[END_REF]. Videos are simply represented using an average CNN activation along time. The bilinear form is trained on the Movie Description dataset described above. The alignment score is a linear combination of several features, including the aforementioned bilinear form, priors and similarities between dialogues. Eventually, the alignment is recovered using a CRF model with well tailored pairwise potentials.

Another line of work consist in aligning web videos with corresponding steps of a cooking recipe [START_REF] Malmaud | What's cookin' ? interpreting cooking videos using text, speech and vision[END_REF]

Temporal models for video

Action models

Action recognition in videos, and more generally video understanding has an inherent temporal aspect. In the past decade, state-of-the-art video descriptors have been based on local variations of pixel values in space but also time. Different feature point and descriptors have been proposed [START_REF] Laptev | On space-time interest points[END_REF], Wang et al., 2011]. However, the global temporal structure of the video has not always been modeled. In this section, we will describe some action recognition and video understanding papers that try to include a global temporal model.

A first attempt at including a video-level temporal structure for action recognition is presented in [START_REF] Laptev | Learning realistic human actions from movies[END_REF]. The idea consists in splitting the video volume into bins, and compute bag-of-words representations inside these. This is very similar in spirit to the spatial pyramids for image classification [START_REF] Lazebnik | Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories[END_REF]. The paper proposes an extensive evaluation of this scheme on the KTH and movie action datasets. Different spatio-temporal tilings are tried and experiments show that different splits are optimal for different actions. For instance, the action "Kiss" does not require any tiles, while "AnswerPhone" works best when splitting the video into 3.

Most action recognition datasets are composed of video clips that are associated with an action label. The actual action is happening somewhere in the video but often the temporal boundaries of the video clip are arbitrary. Several papers try to cope with the problem of automatically finding the best temporal bounds to learn a better model [Duchenne et al., 2009, Satkin and[START_REF] Satkin | Modeling the Temporal Extent of Actions[END_REF]. In Duchenne et al.

[2009], as explained before, the goal is to clean up the temporal bounds that were obtained from a movie script. The authors propose a discriminative clustering cost function based on the hinge loss and optimize it using a coordinate descent approach.

The algorithm alternates between finding the optimal model and selecting the most discriminative part of the video. The work described in [START_REF] Satkin | Modeling the Temporal Extent of Actions[END_REF] is very similar in spirit but comes from another motivation. In order to improve A somewhat similar idea is presented in a work published around the same time [START_REF] Gaidon | Actom sequence models for efficient action detection[END_REF]. The authors propose a structured model for action recognition based on a sequence of "actoms". Each actom is a key step in realizing an action; for instance, for the action "drinking" it could correspond to pouring the drink, lifting the glass and then actually drinking. In order to describe an action, features are pooled around an actom's location, using a weighting scheme which depends on the distance to the A temporal model for action segmentation is proposed in Nguyen et al. [2011]. The task the authors aim at solving is video segmentation: the video is cut into segments and each segment is associated with a label. An action classifier is trained on a set of videos with provided segmentation. Then at test time, the optimal temporal segmentation is obtained by solving a well suited optimization problem. The cost function encourages selecting a segmentation such that the margin between the best class and the second best is maximized. This problem can is then solved using dynamic programming. Overall, this approach can be seen as a way to perform non-maximum suppression in time for action detection. An empirical evaluation is conducted on two datasets, one composed of bee motion trajectories and on a dataset composed of concatenated video clips from an action classification set.

An interesting structured approach to action recognition was proposed in [START_REF] Lan | Discriminative figure-centric models for joint action localization and recognition[END_REF].

Composite activities

Apart from proposing temporally structured model for recognition of individual actions, some works focus on composite activities. These are composed of a sequence of actions, with complex interactions between individual agents and objects. This can be seen as a "macro" scale approach to action recognition, where a whole scene is composed of shorter events. A perfect illustrative example is sport videos, where an event is composed of multiple actions performed by many players.

A rich temporal model of actions is proposed in [START_REF] Gupta | Understanding videos, constructing plots learning a visually grounded storyline model from annotated videos[END_REF]. The authors describe a complex video understanding model based on AND-OR graphs. Nodes of the graph represent elementary actions, for instance in the context of baseball games:

"Run", "Throw", "Miss"... The graph describes causal relations between these actions, in the form of AND-OR relations. For example, after pitching, either the batter can "Hit" OR "Miss". The work described in this paper aims at simultaneously building this relational graph and parsing the corresponding videos accordingly. This implies associating a valid storyline in the graph with tracks of people in the video. The optimal model is obtained using an alternate optimization scheme, iterating between modifying the graph and fitting the graph to a video. Fitting the graph to the video is itself an alternate optimization, switching between the association of nodes to tracks and finding optimal parameters for each action (node). The tackled problem is very hard and the proposed model very ambitious, and it relies on a good heuristic initialization. [START_REF] Kwak | Scenario-based video event recognition by constraint flow[END_REF] propose a composite activity recognition based on a scenario constrained model. A scenario describes how atomic events (called primitives) are temporally related by predicates. These relational predicates allow to encode that some primitives happens before others, byt also the exclusion of two primitives and Another approach at composite activity recognition is proposed in [Rohrbach et al., 2012b]. In this work, composite activities correspond to cooking recipes while the low-level, atomic attributes are activities (peeling or washing) and participants (knife, cucumber). The authors propose to use a pre-trained attribute scoring function at each frame of the video. Several features are computed using these scores, by taking the maximal score along time, or a coocurence of scores. This allows to build the final feature representation for the video sequence. Composite activities are recognized using standard classification algorithms (SVM or nearest neighbors) using this representation as input. An interesting improvement is proposed, where features of this representation (corresponding to low level attributes) are weighted using outside script data. This corresponds to weighting participants and activities using cooking recipes available on-line. In the experimental evaluation, best performance is obtained when using nearest neighbors along with this pre-computed feature weighting. The proposed approach had the great advantage of working for videos picturing composite activities that were not seen in the training videos (but seen in the cooking recipes).

Learning and optimization

Discriminative clustering

Discriminative clustering is an unsupervised method that partitions data by minimizing a discriminative objective. The models correspond to learning a classifier and optimizing over both classifiers and labels [Bach andHarchaoui, 2007, Xu et al., 2004].

They partition the data into clusters, such that these clusters are easily modeled using a classifier of the same class. This kind of models, and their extentions have been used in computer vision and natural language processing. We will review some of the applications from the litterature in this section.

Some convex formulations and relaxations of discriminative clustering have been explored in the past. In particular, [START_REF] Bach | Diffrac: a discriminative and flexible framework for clustering[END_REF] propose a clustering objective based on linear models along with the squared loss. The resulting optimization problem is NP hard and a relaxation of a lifted, equivalent problem is proposed.

We will review this model in detail in Chapter 3 and all our contributions are based on this framework. Related to the limitations of discriminative clustering models and their trivial solutions, [START_REF] Guo | Convex Relaxations of Latent Variable Training[END_REF] describe a convex relaxation for latent variable expectation maximisation and discuss the trivial solutions. They show that these solutions can be avoided as long as one works with the equivalence re-lations between hidden variables instead (corresponding to the lifting employed in DIFFRAC).

In computer vision these discriminative clustering models have been successfully applied to co-segmentation. [START_REF] Joulin | Discriminative Clustering for Image Co-segmentation[END_REF] formulate the co-segmentation problem as a clustering one and use a cost function composed of two terms. One of them, responsible of spatial coherence of the segmentation is based on normalized cuts while the second one is similar to DIFFRAC. The optimization is performed in the lifted equivalence matrix space, using an algorithm for optimization on matrix manifolds [START_REF] Journée | Low-rank optimization on the cone of positive semidefinite matrices[END_REF]. This work is then extended in [START_REF] Joulin | Multi-class cosegmentation[END_REF]] to a multiclass model, using the softmax loss instead of the squared one. The resulting optimization problem is not convex and is initialized using the model from [START_REF] Joulin | Discriminative Clustering for Image Co-segmentation[END_REF], which can be interpreted as a relaxation.

As mentioned before, an extension of the contribution presented in Chapter 4 is In the natural language processing (NLP) litterature, this kind of clustering based on the squared loss has been used for weakly-supervised relation extraction. [START_REF] Grave | A convex relaxation for weakly supervised relation extraction[END_REF] propose to use a squared-loss objective along with linear constraints to detect relations between entities in text. For instance, detecting the relation BornIn in the sentence "Ernest Hemingway was born in Oak Park". A model for dependency parsing, based on this discriminative clustering criterion, is proposed in [START_REF] Grave | A convex and feature-rich discriminative approach to dependency grammar induction[END_REF]. Similar in spirit to the contribution presented in Chapter 5, the authors propose to use a structured set of constraints. Since a valid dependecy parse of a sentence is a tree, the authors propose to carry out the optimization over the set of spanning trees. As in our contribution, the optimization is performed using the Frank-Wolfe algorihtm which allows to efficiently exploit the structure of the problem. Indeed, the linear minimization oracle over the set of depdency trees corresponds to a minimum spanning tree algorithm.

Frank-Wolfe

In our work we use the Frank-Wolfe algorithm (a.k.a conditional gradient) to minimize our cost function while exploiting the alignment structure of our problem.

The Frank-Wolfe algorithm [START_REF] Frank | An algorithm for quadratic programming[END_REF]Wolfe, 1956, Jaggi, 2013] is a classical convex optimization procedure that permits optimizing a continuously differentiable convex function over a convex compact domain only by optimizing linear functions over that domain. It is particularly well suited for problems where the explicit representation of the domain is complicated but efficient algorithms are available to minimize linear functions over it. As explained in the previous section, this typically include problems with structures such as alignments and trees.

We describe the classical version of this algorithm in Chapter 5. Several other variants exist, including Frank-Wolfe with away steps, pairwise away steps and the fully corrective version. All these variants are described in [START_REF] Jaggi | Revisiting Frank-Wolfe: Projection-free sparse convex optimization[END_REF].

Chapter 3

Background

In this chapter we provide some background on the type of models that we use in this work. In the context of discriminative models, we go through the different levels of supervision that can be used. This will allow us to define the terminology that will be used in the rest of this thesis and clarify the distinctions. In the second part of this chapter we discuss clustering algorithms, in particular the DIFFRAC [START_REF] Bach | Diffrac: a discriminative and flexible framework for clustering[END_REF] framework. Finally we describe how we exploit this discriminative clustering framework, incorporate supervision as constraints and how this changes the problem from clustering to classification.

Learning and supervision

The models that we have designed and that are described in this thesis are weakly supervised. In this section we provide a precise description of what we mean by weak supervision and compare this to other classical supervisory setups. All this is described in the context of learning a discriminative model, for instance a multiclass classifier.

In what follows, let us assume that we have data points that we denote by 𝑥, that live in feature space 𝒳 . Data points can be associated with what we call a label 𝑦 that lives in the label space 𝒴. For instance, in the case of binary classification in a 𝑑 dimensional space, we have 𝒳 = R 𝑑 and 𝒴 = {0, 1}.

Our goal is to learn a discriminative model of our data, capable of predicting a label given a feature. That is, to learn a function 𝑓 : 𝒳 → 𝒴 that we refer to as classifier. We denote the set of classifiers that we consider by ℱ. We call learning when we find the function 𝑓 in ℱ such that some criterion is minimized. The criterion that is used depends on the nature of the supervision that we are given and we describe some scenarios in the next sections.

Fully-supervised learning

The most common setup is the fully supervised one, in which one is provided with an annotated dataset, i.e., a set of 𝑁 pairs indexed by 𝑛 of the form (𝑥 𝑛 , 𝑦 𝑛 ). The goal then is to find the function 𝑓 such that the prediction for each 𝑥 𝑛 is as close as possible to 𝑦 𝑛 . The notion of proximity is measured by a loss function that we will denote by ℓ : 𝒴 × 𝒴 → R + . The problem of finding the optimal function is refered to as the empirical risk minimization and corresponds to the following optimization problem:

min 𝑓 ∈ℱ 1 𝑁 𝑁 ∑ 𝑛=1 ℓ(𝑓 (𝑥 𝑛 ), 𝑦 𝑛 ). (3.1)
In order to avoid overfitting issues, there are some aditional terms in the cost function that act as a regularization over the class of functions. This is however out of the scope of this work and we will not consider regularization for the sake of simplicity.

In many cases, obtaining a label 𝑦 𝑛 for every data point can be quite costly. One can think of applications to biology or medicine, where the annotation has to be done by an expert and requires a lot of time. Many computer vision tasks require costly and complex annotations, image segmentation or action recognition are good examples.

In that case, it is of great practical interest to design methods that can recover a classifier 𝑓 from imprecise data. For instance, in the image segmentation task, one can provide very rough contours of objects, and ignoring the details. In the following section we formalize the notion of imprecise annotation.

Weakly-supervised learning

We call weak supervision the setup in which for each sample 𝑥 𝑛 we don't have a precise label 𝑦 𝑛 but a set of samples 𝒴 𝑛 , typically such that 𝒴 𝑛 ⊆ 𝒴. If for each sample this subset only contains one element, we recover the fully-supervised setup. Otherwise, one can exploit this imprecise information by simply minimizing the best-case discrepancy between the prediction 𝑓 (𝑥 𝑛 ) and elements of 𝒴 𝑛 . That would correspond to the following class of optimization problems:

min 𝑓 ∈ℱ 1 𝑁 𝑁 ∑ 𝑛=1 [ min 𝑦∈𝒴𝑛 ℓ(𝑓 (𝑥 𝑛 ), 𝑦) ] . (3.2)
A simple illustration of such a scenario is trying to learn celebrity classifiers given newspaper pictures [START_REF] Berg | Names and Faces in the News[END_REF]. Every picture contains several samples, one per face in the image, and the label set 𝒴 𝑛 is the set of people mentionned in the caption. Every face is therefore associated with several names and learning a model per identity requires to solve the kind of problem mentionned before.

The label can be seen as a latent variable, where the supervision constrains the space in which the labels lives. All the models described in this thesis rely on this setup, with different label spaces 𝒴 𝑛 .

Unsupervised learning

When no labeling information is provided about the data points, we call that the unsupervised setup. In the context of learning a discriminative model, this leads to what we refer to as discriminative clustering that will be described in detail in Sec. 3.2.2. Using the previously described notation, this would correspond to setting for every sample 𝑛, the constrained label set to 𝒴 𝑛 = 𝒴. Please note that this is on the other side of the spectrum than the fully supervised scenario discussed in Sec. 3.1.1.

The weakly-supervised setup is a middle ground which formally include the two other ones, and solely depends on the cardinality of the sets 𝒴 𝑛 .

Semi-supervised learning

The last scenario that we want to describe is the semi-supervised one. This one is a special case of the weakly-supervised setup in which for a given subset of the dataset, the sets 𝒴 𝑛 are singletons. That means, on one part of the dataset we have access to full supervision while on the rest we don't. Let us suppose that we have full supervision for the first 𝑆 elements of the dataset, so for 𝑛 = 1, . . . , 𝑆, 𝒴 𝑛 = {𝑦 𝑛 }. In this setup, the optimization problem we try to solve is the following:

min 𝑓 ∈ℱ 𝛼 𝑆 𝑆 ∑ 𝑛=1 ℓ(𝑓 (𝑥 𝑛 ), 𝑦 𝑛 ) + 1 -𝛼 𝑁 -𝑆 𝑁 ∑ 𝑛=𝑆+1 [ min 𝑦∈𝒴𝑛 ℓ(𝑓 (𝑥 𝑛 ), 𝑦) ] , (3.3)
where 𝛼 is a weighting parameter allowing us to control the influence of labeled versus unlabeled data. In practice properly setting this weight is important and has a big impact on the final performance.

In all these scenarios there are mutliple choices for the set of functions ℱ, the loss ℓ and the label set 𝒴 𝑛 .

Clustering

In the previous section we have discussed different levels of supervision that one can have when learning discriminative models. In the unsupervised case however, the concept of learning class models becomes what we refer to as clustering. When clustering data points, the goal is to group them into clusters such that some criterion is minimized. Grouping points does not link them to any particular element of 𝒴 and the same objective value could be obtained by permuting the labels. In that case, labels only act as an equivalence class between data points: two points share the same label if they are in the same cluster.

In this section we will discuss clustering models and how we adapt them to suit our needs. We will start by discussing generative clustering models such as k-means, followed by a generic description of discriminative clustering. Most of our work relies on the DIFFRAC framework [START_REF] Bach | Diffrac: a discriminative and flexible framework for clustering[END_REF]] that we will describe in detail in Sec. 3.2.3. eventually, we will describe the shift between clustering and classification and how do we impose constraints on a clustering method.

Generative clustering

We will first briefly discuss generative clustering, in particular the k-means clustering model. The goal is to partition data points into 𝐾 clusters, and represent each cluster by the average of its members. The criterion that is optimized is the distance between the members of the cluster and the average representant. This problem is known to be NP-hard and approximate alternate optimization schemes are used, typically Lloyd's algorithm [START_REF] Stuart | Least squares quantization in PCM[END_REF]. In the following we will try to give this model a formal description, that will allow us to draw parallels with the kind of models that we use in this thesis.

Suppose that we have 𝑁 data points, indexed by 𝑛 and that each point 𝑥 𝑛 lives in R 𝑑 . We want to assign each point to one of the 𝐾 clusters. For each point 𝑛, we define an assignment variable 𝑦 𝑛 in {0, 1} 𝐾 , such that the 𝑘 -𝑡ℎ entry of 𝑦 𝑛 is equal to one if the point 𝑛 is assigned to the 𝑘-th cluster. For each cluster 𝑘 we define a representant 𝜇 𝑘 also living in R 𝑑 . If we denote by 𝑀 the matrix in R 𝑑×𝐾 , whose columns are the 𝜇 𝑘 , the product 𝑀 𝑦 𝑛 gives us the representant of the cluster to which the 𝑛-th point is assigned to. Using this notation, the criterion formulated in the previous paragraph can be simply written as:

𝑁 ∑ 𝑛=1 ‖𝑥 𝑛 -𝑀 𝑦 𝑛 ‖ 2 2 . (3.4)
This criterion has to be minimized both in 𝑀 and in all the 𝑦 𝑛 .

The optimization domain for the 𝑦 𝑛 is discrete, and even with a continuous domain, the objective is not jointly convex in the two variables. The classical approximate algorithm consists in doing an alternate optimization. For each 𝑛, we obtain the 𝑦 𝑛 by selecting the column in 𝑀 which is the closest to 𝑥 𝑛 . The 𝑘-th column of 𝑀 can in turn be updated by computing the average of all the 𝑥 𝑛 that are assigned to cluster 𝑘. In contrast, in the following section we will describe the discriminative clustering approach.

Discriminative clustering

The goal of discriminative clustering is to group data points into clusters that are easy to discriminate from each other. That means that each cluster is a class for which it is easy to have a discriminative model for. Using the notation from Sec. 3.1, the general formulation of a discriminative clustering problem can be written as follows:

min 𝑓 ∈ℱ 𝑁 ∑ 𝑛=1 [ min 𝑦∈𝒴 ℓ(𝑓 (𝑥 𝑛 ), 𝑦) ] . (3.5)
For each data point 𝑛, we select a label in 𝒴 such that it will be easy to find a suitable classifier function 𝑓 . Various choices for ℓ and ℱ lead to different algorithms and results, some of which were discussed in Chapter 2. In the following section, we will describe in detail this model in the case where ℱ is the set of linear (or affine) functions and ℓ is the square loss.

DIFFRAC

The DIFFRAC framework introduced in Bach and Harchaoui [2007], is a discriminative clustering model where the classifier is linear and the loss is the square loss.

We will describe here in detal this framework as much of the work presented in this thesis is based upon it. As before, suppose that we are given 𝑁 data points 𝑥 𝑛 in R 𝑑 indexed by 𝑛. Suppose for now that every point is assigned a label, that we represent by an indicator vector 𝑦 𝑛 in {0, 1} 𝐾 . The label vector is binary and sums up to one:

𝑦 ⊤ 𝑛 1 𝐾 = 1
, where 1 𝐾 is the vector composed of ones in dimension 𝐾. We choose the classification function as follows:

𝑓 (𝑥) = arg max 𝑘∈{1,...,𝐾} ℎ 𝑘 (𝑥), (3.6)
where ℎ 𝑘 is the linear scoring function for class 𝑘. For each class 𝑘, we define it as follows:

ℎ 𝑘 (𝑥) = 𝑤 ⊤ 𝑘 𝑥 + 𝑏 𝑘 . (3.7)
where 𝑤 𝑘 is a vector in R 𝑑 and 𝑏 𝑘 is a real-valued scalar. If we stack all the 𝑤 𝑘 into a 𝑑 × 𝐾 matrix 𝑊 and the 𝑏 𝑘 into a 𝐾-dimensional vector 𝑏, we can define the vector scoring function ℎ : R 𝑑 → R 𝐾 :

ℎ(𝑥) = 𝑊 ⊤ 𝑥 + 𝑏. (3.8)
Choosing the square loss, the function ℎ can be found by solving the following optimization problem [START_REF] Hastie | The Elements of Statistical Learning: Data Mining, Inference and Prediction[END_REF]:

min 𝑊 ∈R 𝑑×𝐾 , 𝑏∈R 𝐾 1 𝑁 𝑁 ∑ 𝑛=1 ‖𝑦 𝑛 -𝑊 ⊤ 𝑥 𝑛 -𝑏‖ 2 2 .
(3.9)

Let us define the design matrix 𝑋 in R 𝑁 ×𝑑 whose 𝑛-th row is 𝑥 ⊤ 𝑛 . Similarily, we define the label matrix 𝑌 in {0, 1} 𝑁 ×𝐾 whose 𝑛-th row is 𝑦 ⊤ 𝑛 . Using this notation, the problem can be written in a more compact, matricial form as:

min 𝑊 ∈R 𝑑×𝐾 , 𝑏∈R 𝐾 1 𝑁 ‖𝑌 -𝑋𝑊 -1 𝑁 𝑏 ⊤ ‖ 2 𝐹 , (3.10)
where ‖.‖ 𝐹 denotes the matrix frobenius norm.

However, in the case of DIFFRAC, the label matrix 𝑌 is not known a priori, and is what we want to recover. Let us replace this matrix 𝑌 by a latent variable 𝑍 over which we will optimize our cost function. To simplify notation, we will denote by 𝒵 the set of binary matrices 𝑍 in dimensions 𝑁 × 𝐾 such that 𝑍1 𝐾 = 1 𝑁 (sums up to one along rows). Then our discriminative clustering problem can be written as follows:

min

𝑍∈𝒵 [ min 𝑊 ∈R 𝑑×𝐾 , 𝑏∈R 𝐾 1 𝑁 ‖𝑍 -𝑋𝑊 -1 𝑁 𝑏 ⊤ ‖ 2 𝐹 + 𝜆‖𝑊 ‖ 2 𝐹 ] . (3.11)
The inner optimization over parameters 𝑊 and 𝑏 can be carried out in closed form and yields the following expressions:

𝑊 * = (𝑋 ⊤ Π 𝑁 𝑋 + 𝑁 𝜆𝐼 𝑑 ) -1 𝑋 ⊤ Π 𝑁 𝑍, (3.12) 𝑏 * = 1 𝑁 (𝑌 -𝑋𝑊 * ) ⊤ 1 𝑁 , (3.13)
where 𝐼 𝑑 is the identity matrix in dimension 𝑑 and Π 𝑁 is the centering matrix in dimension 𝑁 :

Π 𝑁 = 𝐼 𝑁 -1 𝑁 1 𝑁 1 ⊤ 𝑁 .
Using these optimal parameters, our problem is equivalent to:

min 𝑍∈𝒵 Tr ( 𝑍𝑍 ⊤ 𝐴 ) , (3.14)
where 𝐴 is a matrix that depends on the data 𝑋 and on the regularization parameter

𝜆: 𝐴 = 1 𝑁 Π 𝑁 ( 𝐼 𝑁 -𝑋(𝑋 ⊤ Π 𝑁 𝑋 + 𝑁 𝜆𝐼 𝑑 ) -1 𝑋 ⊤ ) Π 𝑁 . (3.15)
The problem formulated in Eq. 3.14 is a integer quadratic program. We can easily see that it does indeed correspond to a clustering problem as the cost function does not depend on the permutation of labels. Indeed, if we permute the columns of the matrix 𝑍, the product 𝑍𝑍 ⊤ remains identical and therefore yields the same objective.

It does not matter for a given sample to which class it belongs to, only with which samples does it share this class.

This is even more general, the cost function is invariant to multiplication of 𝑍 by a orthogonal matrix in dimension 𝐾. Indeed, let 𝑂 be such a matrix, then 𝑍𝑂(𝑍𝑂) ⊤ = 𝑍𝑍 ⊤ . Given this observation, the authors propose to perform a lifting, and define a variable 𝑀 = 𝑍𝑍 ⊤ such that 𝑍 is in 𝒵. Let us call the set of such equivalence matrices as ℳ. We can have an explicit description for ℳ as follows:

ℳ = {𝑀 ∈ {0, 1} 𝑁 ×𝑁 , 𝑀 = 𝑀 ⊤ , 𝑀 ⪰ 0, rank(𝑀 ) ≤ 𝐾, diag(𝑀 ) = 1 𝑁 }. (3.16)
Different optimization algorithms can be used to solve problem over this domain.

The one presented in [START_REF] Bach | Diffrac: a discriminative and flexible framework for clustering[END_REF] involves performing a relaxation, by changing some of the constraints; the resulting relaxed problem can be solved as an SDP. Further relaxations allow to write the optimization problem as an eigenvalue problem, which can be solved using standard algorithms. [START_REF] Joulin | Discriminative Clustering for Image Co-segmentation[END_REF] propose to solve the same optimization problem following [START_REF] Journée | Low-rank optimization on the cone of positive semidefinite matrices[END_REF], a method for optimization on the manifold of low rank semidefinite matrices. However, in our case, working with the equivalence matrix is unpractical as it does not allow to impose class specific constraints.

Adding constraints

In our work however, we do care about the "meaning" of classes and want to incorporate constraints on 𝑍. We not only want to group faces of a given character in the same cluster, but we also want to make sure that they correspond to "Jack". Classspecific constraints are impossible to impose on the equivalence matrix 𝑀 described in the previous section. The only kind of additional information that one can impose on 𝑀 are must link and must not link constraints. As we will describe in the following chapters, we want to impose constraints that we derive from the text associated with video as well as structural constraints on 𝑍. Therefore, we do not perform the lifting and solve the quadratic problem under constraints on 𝑍 directly.

The fact that we impose constraints on 𝑍 that are class specific, changes the problem from clustering to weakly-supervised classification. The constraints that we use usually do not present symmetries with respect to classes. For instance, in Chapter 4, we will describe how we model that at least one sample amongst a subset is of a given class. This kind of constraints applies to a given column of 𝑍 and therefore breaks the symmetries. The change from a totally unsupervised setup to a weakly-supervised one is very subtle however.

The framework that we developped in this thesis is very flexible and allows a wide range of applications. Using the same kind of cost functions, and solely changing the amount of constraints, one can move from clustering on one hand to fully supervised classification on the other. These constraints come in our case from structural assumption and meta-data. As soon as an assumption can be written as a linear equality or inequality constraint, it can be directly added to the framework. In the following chapter, we will describe how constraints can be derived from script data to guide person and action recognition in movies.

57

Chapter 4

Weakly supervised labeling of persons and actions in movies

Abstract

In this chapter, we address the problem of recognizing characters and actions in movies using weak supervision provided by scripts. We formulate the recognition as an optimization problem with a cost function composed of two terms, one that is based on discriminative clustering, and a normalized cuts one. We extract character/action pairs from the script and use them as constraints for the aforementioned problem. The corresponding optimization problem is a quadratic program under quadratic constraints. People in video are represented by automatically extracted and tracked faces together with corresponding motion features. We apply the proposed framework to the task of learning names of characters in movies and show significant improvements over previous methods used for this task. Second, we explore joint character/action constraints and show its advantage for weakly supervised action recognition. We demonstrate the performance of our model by localizing and recognizing characters and their actions in feature length movies Casablanca and American Beauty.

Introduction

As mentioned in the introduction, most of recent advances in computer vision rely on supervised learning. This is true in a variety of different tasks: image categorization, object detection, facial identification or action recognition. However, manual annotations are typically expensive to obtain and fully annotating a whole movie is a In this chapter we describe an alternative source of weak supervision, and present a model that takes the temporal imprecisions of this supervision into account. We specifically focus on the problem of character identification and action recognition in feature movies. As mentioned before, for video data such as movies, shooting scripts can easily be found on the web. Scripts contain a lot of information, including people's names, their actions, interactions and emotions, object properties, scene layouts and more. This kind of data has been used as supervision for automatic annotation of characters in TV series in the past [START_REF] Cour | Learning from ambiguously labeled images[END_REF][START_REF] Vignesh Ramanathan | Linking people in videos with "their" names using coreference resolution[END_REF], Sivic et al., 2009[START_REF] Tapaswi | Knock! Knock! Who is it?" probabilistic person identification in tv-series[END_REF]. Scripts have also been used as supervisory signal for action recognition [START_REF] Duchenne | Automatic annotation of human actions in video[END_REF][START_REF] Laptev | Learning realistic human actions from movies[END_REF][START_REF] Marszalek | Actions in context[END_REF].

Using textual descriptions to learn character and action models remains difficult due to the lack of precise temporal and spatial alignment. Usually, every scene description or dialogue has only a rough position in time. In practice, video scripts provide no spatial localization of people or objects, and the temporal localization of events is often imprecise. Moreover, the description is in natural language, and needs to be encoded somehow into a convenient representation.

In this chapter, we observe that the description of a scene often involves objects, people and actions. Knowing that "Rick sits down" in a piece of video can help recognizing what a "sitting down" action is if we can localize "Rick", and vice versa (see Figure 4-1). The main point is that recognizing characters can be useful for learning models of infrequent actions (e.g. hand shaking). We follow this intuition and address joint weakly supervised recognition of characters and actions by exploiting their cooccurrence in movies. Contrary to prior work, we use character-action co-occurrences derived from scripts to constrain the weakly supervised optimization problem. An example output of our algorithm for a short movie clip and the associated script section is shown in Figure 4-1.

Contributions of this chapter.

The contributions presented in this chapter are threefold: (i) We consider a rich use of textual information, that goes beyond using character names. We constrain both person and action recognition using pairs of names and actions co-occurring in the text. (ii) We develop a clustering model jointly labeling actions and people, and incorporating text annotations as constraints. The corresponding optimization is formulated as a quadratic program under quadratic constraints. We propose a convex relaxation that we solve as a sequence of quadratic programs. (iii) We demonstrate the validity of the model on two feature-length movies and the corresponding movie scripts, and demonstrate improvements over earlier weakly supervised methods. This chapter is based on an article presented at ICCV 2013 [START_REF] Bojanowski | Finding Actors and Actions in Movies[END_REF], but includes some additions: first, we propose to include a normalized-cut cost based on descriptor similarity for face identification. Second, we introduce exclusion constraints which prevent the model from predicting the same character for two simultaneous tracks. We demonstrate an improvement in performance for character recognition for both of the proposed modifications.

Joint Model of characters and Actions

In this section, we formulate the problem of jointly recognizing characters and actions in movies. We pose this problem as the minimization of a quadratic cost function under constraints [Bach andHarchaoui, 2007, Joulin et al., 2010]. We incorporate text-based knowledge as a suitable set of constraints on the cluster membership matrices.

Notations and problem formulation

Let us suppose that we have two label sets 𝒫 and 𝒜. We define the sizes of these sets as |𝒫| = 𝑃 and |𝒜| = 𝐴. In practice, one can think of these label sets as person and action classes. Their construction will be discussed in the following sections.

Let us suppose that we are given 𝑁 data points. You can think of these data points as person tracks in a movie. For every sample 𝑛 ∈ {1, . . . , 𝑁 } we are provided with two feature vectors 𝜑 𝑛 and 𝜓 𝑛 in R 𝑑 . We use the same dimension for both features to make the notations less cumbersome. We define the matrices Φ and Ψ in R 𝑑×𝑁 as the horizontal concatenation of all the individual vectors. You can think of these features as of face and action descriptors respectively.

Every sample 𝑛 belongs to a class in 𝒫 and a class in 𝒜. The sample class membership is a priori unknown. For each sample we define a "person" latent variable 𝑧 𝑛 in {0, 1} 𝑃 such that 𝑧 𝑇 𝑛 1 𝑃 = 1. Similarly, we define an "action" variable 𝑡 𝑛 in {0, 1} 𝐴 such that 𝑡 𝑇 𝑛 1 𝐴 = 1. These variables indicate to which person and action class the sample is assigned. In the following, we will denote the 𝑝-th element of a vector 𝑧 𝑛 as 𝑧 𝑛𝑝 .

We define, 𝑍 as a 𝑃 × 𝑁 matrix with columns 𝑧 𝑛 and 𝑇 as a 𝐴 × 𝑁 matrix with columns 𝑡 𝑛 . To simplify the notations, we will denote by 𝒵 and 𝒯 the sets composed of all matrices 𝑍 and 𝑇 respectively:

𝒵 = {𝑍 ∈ {0, 1} 𝑃 ×𝑁 , such that 𝑍1 𝑃 = 1 𝑁 } 𝒯 = {𝑇 ∈ {0, 1} 𝐴×𝑁 , such that 𝑇 1 𝐴 = 1 𝑁 }
Given weak supervision that we will describe later, our goal is to recover the latent variables 𝑍 and 𝑇 . We formulate our problem as follows: where 𝐷 and 𝐺 are cost functions that we will describe in section 4.2.2. The weak supervision we use is represented by the function 𝐶 in the constraints and will be described in section 4.2.4.

Discriminative loss

The problem formulated in the previous section has a cost function composed of two terms 𝐷 and 𝐺. We use a discriminative clustering cost for the definition of 𝐷.

Let us denote by ℱ the set of person classifiers 𝑓 : R 𝑑 → R 𝑃 and by 𝒢 the set of action classifiers 𝑔 : R 𝑑 → R 𝐴 . We denote by Ω a convex regularization function over the set of classifiers of interest: Ω : ℱ × 𝒢 → R + .

Let us consider two multi-class loss functions:

ℓ 𝑃 : {0, 1} 𝑃 × R 𝑃 → R + , ℓ 𝐴 : {0, 1} 𝐴 × R 𝐴 → R + .
When supervision is available for data samples, and learning the classifiers is done by minimizing the empirical risk:

min 𝑓 ∈ℱ 𝑔∈𝒢 1 𝑁 𝑁 ∑ 𝑛=1 ℓ 𝑃 (𝑧 𝑛 , 𝑓 (𝜑 𝑛 )) + 1 𝑁 𝑁 ∑ 𝑛=1 ℓ 𝐴 (𝑡 𝑛 , 𝑔(𝜓 𝑛 )) + Ω(𝑓, 𝑔). (4.2)
In our problem, however, the sample class memberships are unknown (𝑧 𝑛 and 𝑡 𝑛 are not given). We will use the same cost function as for the empirical risk minimization, but 𝑍 and 𝑇 being variables. In the following, we use linear classifiers of the form:

𝑓 (𝜑) = 𝑊 𝑇 𝑃 𝜑 + 𝑏 𝑃 , 𝑔(𝜓) = 𝑊 𝑇 𝐴 𝜓 + 𝑏 𝐴 ,
where 𝑊 𝑃 is a matrix in R 𝑑×𝑃 , 𝑏 𝑃 is a vector in R 𝑃 , 𝑊 𝐴 is matrix in R 𝑑×𝐴 and 𝑏 𝐴 is a vector in R 𝐴 . We use for losses ℓ 𝑃 and ℓ 𝐴 the squared Frobenius norms. We define the regularizer Ω by:

Ω(𝑓, 𝑔) = 𝜆 𝑃 ‖𝑊 𝑃 ‖ 2 𝐹 + 𝜆 𝐴 ‖𝑊 𝐴 ‖ 2 𝐹 .
Our cost function becomes:

𝐷(𝑍, 𝑇 ) = min 𝑊 𝑃 , 𝑏 𝑃 𝑊 𝐴 , 𝑏 𝐴 1 𝑁 𝑁 ∑ 𝑛=1 ‖𝑧 𝑛 -𝑊 𝑇 𝑃 𝜑 𝑛 -𝑏 𝑃 ‖ 2 𝐹 + 𝜆 𝑃 ‖𝑊 𝑃 ‖ 2 𝐹 + 1 𝑁 𝑁 ∑ 𝑛=1 ‖𝑡 𝑛 -𝑊 𝑇 𝐴 𝜓 𝑛 -𝑏 𝐴 ‖ 2 𝐹 + 𝜆 𝐴 ‖𝑊 𝐴 ‖ 2 𝐹 .
Using the notations from the previous section, this can also be rewritten in a more compact manner as:

𝐷(𝑍, 𝑇 ) = min 𝑊 𝑃 , 𝑏 𝑃 𝑊 𝐴 , 𝑏 𝐴 1 𝑁 ‖𝑍 -𝑊 𝑇 𝑃 Φ -𝑏 𝑃 1 𝑇 ‖ 2 𝐹 + 𝜆 𝑃 ‖𝑊 𝑃 ‖ 2 𝐹 + 1 𝑁 ‖𝑇 -𝑊 𝑇 𝐴 Ψ -𝑏 𝐴 1 𝑇 ‖ 2 𝐹 + 𝜆 𝐴 ‖𝑊 𝐴 ‖ 2 𝐹 . (4.3)
We get the optimum of the minimization problem with respect to 𝑊 𝑃 , 𝑏 𝑝 , 𝑊 𝐴 and 𝑏 𝐴 as the solution of a ridge regression problem. In particular, for fixed 𝑍 and 𝑇 , setting the gradients with respect to 𝑊 𝑃 , 𝑏 𝑃 , 𝑊 𝐴 and 𝑏 𝐴 to zero yields:

𝑊 𝑃 = (ΦΠ 𝑁 Φ 𝑇 + 𝑁 𝜆 𝑃 𝐼 𝑑 ) -1 ΦΠ 𝑁 𝑍 𝑇 , 𝑏 𝑃 = 1 𝑁 (𝑍 -𝑊 𝑇 𝑃 Φ)1, 𝑊 𝐴 = (ΨΠ 𝑁 Ψ 𝑇 + 𝑁 𝜆 𝐴 𝐼 𝑑 ) -1 ΨΠ 𝑁 𝑇 𝑇 , 𝑏 𝐴 = 1 𝑁 (𝑇 -𝑊 𝑇 𝐴 Ψ)1.
Plugging these expressions back in the cost function yields:

𝐷(𝑍, 𝑇 ) = Tr ( 𝑍 𝑇 𝑍𝐴 ) + Tr ( 𝑇 𝑇 𝑇 𝐵 ) , (4.4)
where:

𝐴 = 1 𝑁 Π 𝑁 ( 𝐼 𝑁 -Φ 𝑇 ( ΦΠ 𝑁 Φ 𝑇 + 𝑁 𝜆 𝑃 𝐼 𝑑 ) -1 Φ ) Π 𝑁 , 𝐵 = 1 𝑁 Π 𝑁 ( 𝐼 𝑁 -Ψ 𝑇 ( ΨΠ 𝑁 Ψ 𝑇 + 𝑁 𝜆 𝐴 𝐼 𝑑 ) -1 Ψ ) Π 𝑁 .
Using kernels. Following [START_REF] Bach | Diffrac: a discriminative and flexible framework for clustering[END_REF], we notice that 𝐴 can be expressed only in terms of the Gram matrix ΦΦ 𝑇 . Therefore, we can use any kernel and replace occurrences of this Gram matrix by the kernel matrix 𝐾. Let us define a kernel for person identities that we will denote 𝐾 𝑃 and one for motion actions that we will denote 𝐾 𝐴 . This gives us the following updated expressions for 𝐴 and 𝐵:

𝐴 = 𝜆 𝑃 Π 𝑁 (Π 𝑁 𝐾 𝑃 Π 𝑁 + 𝑁 𝜆 𝑃 𝐼 𝑁 ) -1 Π 𝑁 , 𝐵 = 𝜆 𝐴 Π 𝑁 (Π 𝑁 𝐾 𝐴 Π 𝑁 + 𝑁 𝜆 𝐴 𝐼 𝑁 ) -1 Π 𝑁 . (4.5)

Grouping term

In addition to the previously described discriminative term 𝐷, we propose to use a normalized-cut term. In the following we restrict ourselves to the person variable 𝑍, but a similar cost can be defined for actions. To this end, we define a graph whose vertices correspond to person tracks and weighted edges encode similarity between these nodes. The weights of the edges are encoded in an 𝑁 × 𝑁 matrix 𝑊 such that:

𝑊 𝑛𝑛 ′ = exp(-𝛾𝑑(𝜑 𝑛 , 𝜑 𝑛 ′ )), (4.6)
where 𝑑 is a distance between the descriptors of the two tracks. We will discuss in details our choice for 𝑑 in the experimental section. We then compute the normalized laplacian of this graph as:

𝐿 = 𝐼 𝑁 -𝑆 -1 2 𝑊 𝑆 -1 2 , ( 4.7)
where:

𝑆 = Diag(𝑊 1 𝑁 ), (4.8)
is the diagonal matrix whose diagonal corresponds to the row sum of the weight matrix 𝑊 . Then, the normalized cut term of our cost function is defined as:

𝐺(𝑍, 𝑇 ) = Tr(𝑍 ⊤ 𝐿𝑍). (4.9)

Constraints on latent variables

In our problem formulation, we propose to use task specific constraints that reduce the search space for 𝑍 and 𝑇 by including information mined from scripts. Using these constraints allows us to add additional knowledge, and has two other important advantages. First, given our cost function, the minimizations with respect to 𝑍 and 𝑇 are totally independent. Adding constraints that depend on both variables will allow us to tie them together. Second, both cost functions defined in this section are symmetric with respect to classes: as for any clustering problem, the objective is invariant to permutations of labels. Nothing really ties a specific cluster to a specific character in the movie. In order to fix this permutation we propose to use constraints on latent variables. We will describe in this section the different constraints that we can generate using the aligned scripts.

Mention Constraints

We want to constrain our problem by coupling person and action labels. We do so by using information mined from movie scripts. After aligning scripts with timestamped subtitles as in [START_REF] Everingham | Hello! My name is... Buffy" -Automatic Naming of Characters in TV Video[END_REF], we get a temporal location for every scene description and closed caption. We remind the reader that a scene description is a set of sentences that describe what is played on screen. A closed caption is a piece of speech, as pronounced by the specified character.

We make the assumption that if the text mentions someone doing something, this action should appear on screen. From the aforementioned data, we can extract personaction couples (𝑝, 𝑎) to generate our constraints. Remember that 𝑝 is an integer in {1, . . . , 𝑃 } and 𝑎 is in integer in {1, . . . , 𝐴}.

We index the scene descriptions by an integer 𝑖 in {1, . . . , 𝐼}. Every scene description is a set of sentences associated with a beginning and end frame (𝑓 𝑏 and 𝑓 𝑒 respectively). We search for person tracks that appear between frames 𝑓 𝑏 and 𝑓 𝑒 . We denote this subset of tracks by 𝒩 𝑖 .

We process the sentences in the scene description 𝑖 to detect person-action pairs.

All occurrence of a subject-verb pair are denoted by a set Λ 𝑖 . Λ 𝑖 contains indexed (𝑝, 𝑎) pairs. If the subject is a pronoun we denote the corresponding tuple as (∅, 𝑎).

For every scene description 𝑖, we can write the following set of equations:

∀(𝑝, 𝑎) ∈ Λ 𝑖 , ∑ 𝑛∈𝒩 𝑖 𝑧 𝑛𝑝 𝑡 𝑛𝑎 ≥ 1, (4.10) ∀(∅, 𝑎) ∈ Λ 𝑖 , ∑ 𝑛∈𝒩 𝑖 𝑡 𝑛𝑎 ≥ 1. (4.11)
Constraints using the (𝑝, 𝑎) pairs couple the two sub-problems. Please note however that the inequalities in Eq. (4.10) are non necessarily convex in general. The inequalities defined using (∅, 𝑎) generate linear constraints on the action latent variables.

Speaker Constraints

We can additionally constraint the problem using the subtitles. Indeed, if a character is speaking at a given time, it is likely he / she will appear in the surrounding video signal. Let us denote by C the set of closed captions for a given movie. For every closed caption c in C, we get the begin and end frame (𝑓 𝑏 and 𝑓 𝑒 ). The character that speaks in the closed caption c will be called 𝑝. We select the set of shots that contains the time interval [𝑓 𝑏 , 𝑓 𝑒 ] and find the person tracks that appear within. Let us denote 𝒩 c this set of tracks for the closed caption c.

For every closed caption c in C, we can write the following constraint:

∑ 𝑛∈𝒩c 𝑧 𝑛𝑝 ≥ 1.
This yields a set of linear constraints on the person latent variable.

Exclusion Constraints

We add another constraint to prevent our model from predicting the same character name for two overlapping tracks. It is reasonable to assume that two overlapping tracks are unlikely to be the same person. The only counter example would be in scenes involving mirrors. We will consider this specific case as an exception that can be handled by the slack variables presented in Sec. 4.2.5.

In order to implement this assumption as a constraint we need to find the set of overlapping tracks. We search for maximal groups of overlapping constraints. To find these maximal groups we first build the graph 𝐺 = (𝑉, 𝐸) of overlaps between tracks.

The nodes of this graph correspond to person tracks. We add an edge between two nodes 𝑣 1 and 𝑣 2 if the corresponding tracks overlap in time.

Finding all the maximal cliques in a graph is a classical NP-complete problem [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. Instead, we first list the set of connected components in this graph.

Because of shot boundaries, most connected components are of reasonable size. If a connected component contains less than 20 nodes, we use the Bron-Kerbosch algorithm [START_REF] Bron | Algorithm 457: Finding all cliques of an undirected graph[END_REF] to list all maximal cliques. Otherwise we limit ourselves to listing all cliques of size 3.

Let us denote by C the set of cliques found using the aforementioned procedure.

For every clique 𝑐 in C , for every label 𝑝 in {1, . . . , 𝑃 }, we can write the following constraint:

∑ 𝑛∈𝑐 𝑧 𝑛𝑝 ≤ 1 (4.12)
This corresponds to a set of linear constraints on 𝑍 and can be easily added to our optimization problem. Please note however that the equivalent constraints for 𝑇 do not hold. Indeed, people can perform the same action simultaneously (quite frequent for some classes: e.g. "Walk").

"Scene Constraints"

Another type of constraints was proposed by Ramanathan et al. [2014]. The authors observe that movies are usually divided into units called "scenes". A scene is a set of shots that take place in the same location and share a narrative thread. The movie scripts we use with our movies are provided with scene indications.

The scene constraints defined by Ramanathan et al. [2014] are the following: If a character name is never mentioned in a scene in the script, he or she never appears on screen in that scene. For a given scene 𝑠 in the script, one has to find the corresponding beginning and end frames (𝑓 𝑏 and 𝑓 𝑒 ) in the video. Let 𝒩 𝑠 ⊂ {1, . . . , 𝑁 } be the set of person tracks appearing between 𝑓 𝑏 and 𝑓 𝑒 .

In the script, within a scene 𝑠, we search for characters that speak or are mentioned in a scene description. Let us call this set of characters 𝒫 𝑠 ⊂ {1, . . . , 𝑃 }. Using the aforementioned sets, we can define the following set of constraints:

∀ 𝑠, ∀ 𝑛 ∈ 𝒩 𝑠 , ∀ 𝑝 / ∈ 𝒫 𝑠 , 𝑧 𝑛𝑝 = 0. (4.13)
These are simple linear equality constraints that can be added to our optimization problem. We do not use this kind of constraints in our model and only include their description for completeness.

External information

Our method allows the use of additional supervised data. For example, the cast of characters can be found, and images of the respective characters can be downloaded from the web. We can also get manually annotated videos corresponding to the action set 𝒜. Supervision can be added to our model by simply appending the corresponding data points to the data matrix. We then constrain the corresponding latent variables to be equal to the provided annotations. This corresponds in the end to adding a set of linear equalities on the matrices 𝑍 and 𝑇 .

Note however that we have to be careful and extract relevant descriptors for these additional examples. The features need to be comparable to those extracted from person tracks in the movie of interest. Indeed, the main application for this kind of constraints is to populate the dummy "background" class. For instance, for person identities, we compute face descriptors of face images randomly sampled from a public face figures dataset. However, the descriptors for face tracks in video and face detections in images differ in number.

Slack Variables

In practice, the constraints we have defined in the previous section can be erroneous. There are many reasons for that, including script mis-alignment, hypotheses not met etc. For instance, a person-action pair in a scene description may not have corresponding person tracks in the video. This can happen due to failures of automatic person detection and tracking.

To cope with these issues, we introduce slack variables allowing the constraints to be violated. We define a slack variable vector 𝜉. Suppose there are in total 𝐽 different constraints. There is one 𝜉 𝑗 per constraint and therefore 𝜉 is a real vector of length 𝐽. We add the slack to every constraint and add a quadratic penalization to our cost

Optimization

The problem we have formulated in the previous section is the minimization of a quadratic cost over a discrete set. This discrete optimization domain is defined by a set of quadratic or linear constraints, that are described in Sec. 4.2.4. In order to make the optimization of our problem tractable, we first relax the optimization domain. Then, since the domain is defined by quadratic constraints, we propose an alternating optimization scheme. We will describe in more details the two procedures in the following section.

Relaxation

Our optimization variables 𝑍 and 𝑇 are defined as binary stochastic matrices. Solving quadratic optimization problems over these sets is known to be NP-hard [START_REF] Schrijver | Combinatorial optimization: polyhedra and efficiency[END_REF]. We therefore propose to use a classical relaxation and replace 𝒵 and 𝒯 by their convex hulls. These convex hulls (respectively 𝒵 and 𝒯 ) correspond to the simplices 𝒮 𝑃 𝑁 and 𝒮 𝐴 𝑁 :

𝒮 𝑃 𝑁 = {𝑍 ∈ [0, 1] 𝑁 ×𝑃 , 𝑍1 𝑃 = 1 𝑁 }, (4.14) 𝒮 𝐴 𝑁 = {𝑇 ∈ [0, 1] 𝑁 ×𝐴 , 𝑇 1 𝐴 = 1 𝑁 }. (4.15)
By replacing the sets 𝒵 and 𝒯 by their convex hulls, our problem becomes a continuous optimization problem.

Splitting the Optimization

As mentioned above, our optimization program minimizes a quadratic cost under several types of constraints. The cost function is a sum of two separate convex quadratic functions of 𝑍 and 𝑇 . The optimization domain 𝒟 is defined by the intersection of sets 𝒵 and 𝒯 , linear equalities on 𝑍 and 𝑇 separately, linear inequalities on 𝑍 and 𝑇 separately and joint quadratic constraints on 𝑍 and 𝑇 . Even though the domain is now continuous, it is not clear whether it is convex.

Quadratic constraints are non convex in general unless the constraint matrix is shown to be positive semidefinite. In our case, the matrices of the quadratic constraints are neither positive nor negative semidefinite. We observe that our relaxed optimization domain is defined as the intersection of potentially non-convex sets.

Therefore, we cannot easily conclude on the convexity of 𝒟 based on that. Because of that, we cannot simply use quadratically constraints quadratic program (QCQP) solvers. We propose to use a simple block-coordinate optimization scheme in order to solve our problem.

We alternate between optimizing in 𝑍 and 𝑇 , fixing the value of the other one.

Please note that we optimize over 𝜉 on both occasions. At every iteration, the quadratic constraints become linear ones in the variable which is optimized. Therefore, each step boils down to the minimization of a quadratic function over a convex set defined by linear constraints. Each of these steps can be solved using an interior-point method.

Many implementations are available online, and we perform our experiments using the MOSEK solver.

We start the algorithm by first freezing the 𝑇 variable and optimizing over 𝑍 and 𝜉. We initialize 𝑇 with the uniform assignment matrix 𝑇 = 1 𝐴 1 𝑁 1 ⊤ 𝐴 .

Rounding

At the end of the optimization of the relaxed problem we have a real valued solution ( Ẑ, T ). However, we want to obtain a feasible point of the jver, 2003]. Because of that, for the rounding procedure, we drop all the aforementioned constraints and simply solve:

max 𝑍∈𝒵 Tr(𝑍 ⊤ Ẑ).
This in turn is solved exactly by independently taking the maximum value along each row of Ẑ. Please note that the constraints that defined the optimization domain in the previous section are dropped. This rounding procedure provided satisfactory performance in our experiments. [START_REF] Bach | Diffrac: a discriminative and flexible framework for clustering[END_REF] Our problem formulation in (4.4) is closely related to the discriminative clustering approach Diffrac [Bach andHarchaoui, 2007, Joulin et al., 2010]. When latent classes are treated equally, the minimization of a convex relaxation of (4.4) results in a trivial solution [START_REF] Guo | Convex Relaxations of Latent Variable Training[END_REF]. To overcome this issue, one can perform a lifting and optimize (4.4) with respect to the equivalence matrix 𝑀 = 𝑍𝑍 𝑇 instead (under a suitable set of constraints).

Relation to Diffrac

Working with 𝑀 is problematic in our case since our constraints in (4.10) are defined on the elements of 𝑍 rather than on 𝑀 . Class-dependent constraints in our case, however, break the symmetry in class labels, and enable (4.4) to be solved directly for 𝑍. In practice we found that modifying the value of 1 to a larger constant on the right sides of inequalities (4.10) leads to a more stable solution of (4.4).

Features and Dataset

Text processing

The method described in this chapter relies on a semantic representation of text.

Indeed, we propose to exploit textual information to constrain our learning problem.

To this end, we need to automatically extract <NAME,ACTION> pairs from natural language. There are many different ways one could do that, and we discuss some of these in this section.

The simplest way one can extract this kind of information from text is to find subjects and verbs. This can be done in an unstructured way using part-of-speech (POS) tagging. However, in a sentence there can be multiple nouns, and multiple verbs, yielding unwanted uncertainties. Some heuristic may be needed to pair nouns to verbs which is a problem on its own.

Another straightforward way is to use the root and direct dependencies of a dependency tree. This reliably provides the main subject and verb for most sentences.

However, even though the detection should be correct most of the time, verbs do not Ilsa quickly walks towards the entrance. correspond to action classes. Verbs could be grouped using some semantic similarity measure from resources such as VerbNet [START_REF] Kipper | A large-scale classification of english verbs[END_REF].

In this work, we propose to extract person-action pairs from text using a semantic role labeling parser. Semantic role labeling consists of identifying arguments (agent, instrument, manner, cause) of a stereotypical situation to a predicate (for example a verb). Intuitively, this amounts to answering questions such as: "Who" does "What", "When", "Where" and "Why"? We define events as entries from the FrameNet database.

This database defines so called "frames" which correspond to templates of an event.

A frame is typically composed of subjects, relations, participants, objects etc. A few sample frames from FrameNet are given for illustration in Table 4.1.

Detecting these frames in natural language is a hard problem, but several statistical parsers are available on-line. In our work we use SEMAFOR [START_REF] Das | An exact dual decomposition algorithm for shallow semantic parsing with constraints[END_REF].

This is a statistical model trained on the annotated data associated with FrameNet.

The performance of this model heavily relies on the quality of the manual annotations, which for some frames can be very scarce. We limit our experiments to two simple frames that occured often enough in the movies we considered and that have an associated agent: "ChangePosture" and "SelfMotion". From each detected occur-Manipulation The words in this frame describe the manipulation of an Entity by an Agent.

Losing

This frame describes a situation in which an Owner loses his or her Possession. The Owner may have failed to keep ownership of their Possession (i.e. robbery or gambling) or may have unintentionally misplaced their Possession.

Self_motion The Self_mover, a living being, moves under its own direction along a Path. Alternatively or in addition to Path, an Area, Direction, Source, or Goal for the movement may be mentioned.

Being_wet

An Item is in a state of wetness with the possibility of the wetting Liquid being mentioned, along with the Degree of wetness.

Table 4.1 -A few sample frames as defined in the FrameNet project [START_REF] Baker | The berkeley framenet project[END_REF]. Every frame comes with lexical units that evoke the frame and a set of frame elements.

In the examples provided here we put the core frame elements (the most important ones) in bold. For instance, lexical units for the frame Manipulation include the following verbs: caress, grab, hold, kiss, pull etc... rence of the frame in the text we use the "agent" and the "target verb" as the name and action pair.

Video features

The aim here is to design a representation of video that can be related to the <person,action> structure extracted from text. We do so by extracting tracks of people from video. Each track is then represented by face appearance features to capture identity and body motion features to represent the action. See Fig. 4-3.

To extract person tracks, we compute face tracks and extrapolate a body bounding box from these. We run the multi-view face detector of [START_REF] Zhu | Face detection, pose estimation, and landmark localization in the wild[END_REF] and associate detections across frames using point tracks in a similar manner to what was proposed by [START_REF] Everingham | Hello! My name is... Buffy" -Automatic Naming of Characters in TV Video[END_REF], [START_REF] Sivic | Who are you?" -Learning person specific classifiers from video[END_REF]. To represent faces we follow the work of [START_REF] Sivic | Who are you?" -Learning person specific classifiers from video[END_REF]: we extract facial features and rectify each face into a canonical frame using a similarity transformation. We re-compute facial feature positions in the rectified image and extract SIFT descriptors at multiple scales from each facial landmark. Finally, each track is represented by the set of descriptors, one for each landmark, for each face in the track.

To represent actions, we compute bag-of-features on dense trajectories [START_REF] Wang | Action recognition by dense trajectories[END_REF] extracted from each person track. We take the trajectories that fall into the spatio-temporal volume defined by the upper-body bounding box in each frame. As mentioned before, the upper-body bounding box is defined here by simply extrapolating the face bounding-box using a hand-crafted linear transformation. This way, we are sure that for every face we always have a corresponding upper-body region. Also, it allows us to get rid of the face to body association problem which can be a problem on its own.

Please note that our discriminative cost function allows the use of kernels. For face tracks, we follow [START_REF] Sivic | Who are you?" -Learning person specific classifiers from video[END_REF] and use the sum of "min-min kernels" computed separately for each facial feature as well as frontal and profile faces. This results in a total of 38 face track kernels (24 for frontal features and 14 for profile features) that are summed with uniform weights. We do not optimize the weights of the kernel mixture as the average has been shown to work well in practice. For motion descriptors, following common practice, we use the exponentiated chi-square kernel [START_REF] Wang | Action recognition by dense trajectories[END_REF].

Dataset

We report results for our method on two full-length feature movies, Casablanca and American Beauty. We process both movies and extract person tracks and associated descriptors (as described in the previous section). We discard person tracks that have unreliable facial features, based on the landmark localization score. For Casablanca, this yields 1,273 person tracks containing 124,423 face detections. For American Beauty we use 1,330 person tracks containing 131,741 face detections.

Please note that our evaluation is person-track dependent: we suppose that undetected faces do not exist. The ground truth does not cover faces that were not detected or dropped due to poor facial features.

By processing the corresponding movie scripts, we extract 17 names for the main characters in Casablanca and 11 names for the main characters in American Beauty. For each movie we select two most frequent action classes (frames), i.e., walking, sit down for Casablanca and walking, open door for American Beauty. For Casablanca we obtain 42 action/name pairs and 359 occurrences of names with no associated actions.

For American Beauty the corresponding numbers are 31 and 330, respectively.

To explicitly model non-named characters in the movie (side characters and extras) as well as unnamed action classes, we introduce an additional "background" class for both faces and actions. However, our model lacks a good definition of what the background class exactly is. In order to add some knowledge about the background, we collect background examples as follows. For faces, we collect 500 additional random faces from the Labeled Faces In The Wild dataset [START_REF] Gary | Labeled faces in the wild: A database for studying face recognition in unconstrained environments[END_REF]. For actions, we randomly sample 500 person tracks from the Hollywood2 dataset [START_REF] Marszalek | Actions in context[END_REF] using the corresponding movie scripts to discard actions considered in this work.

For all "background" samples, we constrain latent variables to take values corresponding to the "background" class. We have found that including this additional data helps resolving confusion in label assignment for our target classes.

Comparison with other weakly supervised methods

Here we compare our method with other weakly supervised face identification approaches. We use the code adapted from [START_REF] Sivic | Who are you?" -Learning person specific classifiers from video[END_REF] and an on-line available implementation of the method described by [START_REF] Cour | Learning from ambiguously labeled images[END_REF]. We run all methods on 1,273 face tracks from Casablanca and 1330 face tracks from American Beauty using noisy name annotations obtained from movie scripts. To have a fair comparison, no action labels are used. While [START_REF] Cour | Learning from ambiguously labeled images[END_REF] and [START_REF] Sivic | Who are you?" -Learning person specific classifiers from video[END_REF] have been evaluated on television series, here we address a more challenging setup of full-length movies. First, the training data within a film is limited as it is not possible to harvest face tracks across multiple episodes as in TV series. Second, the cast of characters in a film is often larger than in TV series with many additional extras. Third, films often employ a wider set of cinematographic techniques compared to often simpler structure of a TV show with many close-ups and "shot-reverse shot" dialogues.

Comparative results for the two movies in Figure 4-5 demonstrate the superior performance of our method. The lower performance of [START_REF] Sivic | Who are you?" -Learning person specific classifiers from video[END_REF] can be explained by the fact that it relies on visual speaker identification and lip motion estimation.

While our adaptation of the code obtained from [START_REF] Sivic | Who are you?" -Learning person specific classifiers from video[END_REF] works well on the data from their paper, we have found that the speaker detection achieves only 64.2% and 50.2% accuracy (with about 25% speaker labeled tracks) on Casablanca and American Beauty, respectively. The lower accuracy, compared to the accuracy of more than 80% on the TV series data from [START_REF] Sivic | Who are you?" -Learning person specific classifiers from video[END_REF], could possibly be due to the challenging illumination conditions with strong shadows present in the two films. The approach of [START_REF] Cour | Learning from ambiguously labeled images[END_REF] assumes that correct labels are included into the set of "ambiguous" labels. This assumption is often violated in movies as side characters and extras are often not mentioned in the script. In contrast, our approach suffers less from this problem since (a) it can handle multiple annotations for bags of multiple tracks and (b) the noise in labels and person detections is explicitly modeled using slack variables.

Learning names and actions

We next evaluate benefits of learning names and actions jointly. This is achieved by first learning the name assignments 𝑍 for all tracks. The name assignments are then fixed and used as additional constraints when learning the likely action assignments 𝑇 for each track. While this procedure can be iterated to improve the assignment of character names with the help of estimated action labels, we found that the optimization converges after the first iteration.

The distribution of action classes in our data is heavily unbalanced with the "background" class corresponding to more than 78% of person tracks. We therefore evaluate the labeling of each target action in each movie using a standard one-vs-all action precision-recall measure. We compare the following methods: Names+Actions corresponds to our proposed method of learning person names and actions jointly.

No Names uses constraints on actions only without considering joint constraints on actions and names. True Names+Actions uses the ground truth person names as constraints on actions instead of the automatic name assignment. This provides an upper bound on the action classification performance provided perfect assignment of person names. Finally, we evaluate two "dummy" baselines which blindly assign action labels based on person names and person-action pairs obtained from scripts.

The purpose of these baselines is to verify that visual action classification improves the performance. Names+Text learns face assignments for each person track and assigns action labels using person-action pairs. True Names+Text assigns action labels based on person-action pairs and ground truth person names. This baseline, hence, does not "look" at image pixels at all. Note that the last two baselines produce a single point on the precision-recall plot as no confidence values are available when transferring action labels from scripts.

Precision-recall plots for the target action classes in two movies are shown in Figure 4-6. We first observe that our full method (blue curves) outperforms the weakly supervised learning of actions only (green curves) in most of the cases. This shows the benefit of learning actions and names jointly. As expected, action classification can be further improved using ground truth for name assignments (red curves).

For the frequent action walking for which many person-action constraints are available in scripts, automatic person naming in our method provides a large benefit.

However, even with ground truth face assignments the action classification performance is not perfect (True Names+Actions). This is likely due to two reasons. First, the ambiguity in the weak supervision is not reduced to zero as a single character may do several different actions in a single clip (bag). Second, the current action representation could be significantly improved.

Recognizing less frequent actions sit down and open door appears to be more difficult. While several examples are ranked high, all methods suffer from a small number of available person-action constraints. In addition, a significant portion of these constraints is incorrect. Incorrect constraints often occur due to the failure of face detection as characters often turn away from the camera when sitting down and opening doors. To explicitly quantify the loss due to failures of automatic person tracking, we have manually annotated person tracks in the movie Casablanca. The performance of our full method is significantly improved when run on correct person tracks yielding AP=0.36 and AP=0.63 for the sit down and walk actions, respectively. This emphasizes the need for better automatic person detection and tracking methods.

Qualitative results for automatic labeling names of characters and actions using our method (Names+Actions) are illustrated in Fig. 4567.

We show sample qualitative results obtained on the movie Casablanca in Fig. 4567.

Improvements

We propose in this thesis two main improvements to the model which was first proposed in [START_REF] Bojanowski | Finding Actors and Actions in Movies[END_REF]: adding a grouping term and uniqueness constraints. We want to experimentaly validate these improvements by showing that they yield better performance for the task of person recognition. To this end we run our algorithm, and limit ourselves, as in Sec. 4.6.2, to the face recognition part. We optimize the model with and without using both the grouping term and the exclusion constraints. We use exactly the same setup and performance measure as in the aforementioned section. Empirical results computed for both Casablanca and American Beauty are presented in Fig. 4-8. We observe a significant improvement due to the two model modifications that we propose. For both movies, adding a grouping term and using exclusion constraints boosts the performance by 7%. It is interesting to notice that most of the improvement is due to the use of a grouping term. However, both modifications contribute to the higher average precision, as we see by looking at partially stripped-down versions of the model. When using the grouping term, the exclusions constraints seem to contribute to performance at high recall (propotion of labeled tracks).

Conclusion and future work

In this chapter, we have presented a new weakly supervised model to jointly recognize actions and characters in video. We have shown that the model can be apllied on feature-length movies together with their shooting scripts. We demonstrated a significant improvement over other weakly supervised methods for person recognition in movies with associated descriptions. Our experiments on action recognition show the benefits of recognizing the agent of the action. We believe that this kind of joint representation will help automatic video understanding, both at the level of local action models and global plot understanding.

The main limitation of this work is that the vocabulary of actions is very limited. In order to move towards larger vocabularies, and higher number of samples, one needs to work on many more movies. As actions are shared across movies, applying the model over multiple movies simultaneously opens-up the possibility of automatically learning classifiers for a large vocabulary of action classes.

Figure 5-1 -Illustration of the problem addressed in this chapter. Given a video as a stream of frames and a text as a stream of sentences, we want to recover the temporal correspondence between frames and sentences. The problem is weakly supervised as we know that the assignment needs to respect the temporal order constraint.

Recently, several models have been proposed for automatic video description. Data for training joint video and text models is quite abundant and easy to find. Indeed, movies are often available along with their shooting scripts, sport events are associated with commentaries, and online "do it yourself" videos are often paired with a step-bystep recipies. The textual descriptions found in such paired text/video data precisely describe events that are happening on the screen. Manually corrected datasets composed of videos with textual descriptions have been proposed and have been used to train joint models.

However, exploiting such paired textual and video data is hard for several reasons.

First of all, the descriptions are not always perfect and present a significant amount of noise. For instance, shooting scripts do not always correspond to what was shown in the final movie due to editing or actor's performance. In "how to" videos, the narrator sometimes anticipates future events instead of describing what he is doing at a given time. Second, there is a strong uncertainty in the temporal and spatial correspondence between the text and the video. As for image captioning, there is no spatial relation between nouns and objects, and additional uncertainty comes from the temporal dimension.

In this work, we cope with this temporal uncertainty and build a joint text and video model capable of recovering the temporal correspondence between sentences 𝐷 × 𝐼 and 𝐸 × 𝐽 matrices.

In the context of video to text alignment, Φ is a description of the video signal, made up of 𝐼 temporal intervals while Ψ is a textual description, composed of 𝐽 sentences (or, more generally, text fragments). Every 𝜓 𝑗 is the representation of sentence 𝑗, for instance its term-frequency representation. If applied to videos with a corresponding sequence of labels, Ψ is the sequence of labels, composed of 𝐽 elements.

Then every 𝜓 𝑗 is simply the indicator vector of the 𝑗-th class in the sequence. We focus in this chapter on video to text alignment, but our model is general and can be applied to other types of sequential data (biology, speech, music, etc.). In the rest of the chapter, except of course in the experimental section, we consider the abstract problem, considering two generic data stream modalities.

Our goal is to map every element 𝑖 in {1, . . . , 𝐼} to an element 𝑗 in {1, . . . , 𝐽}. At the same time, we also want to learn a linear map between the two feature spaces, parametrized by 𝑊 in R 𝐸×𝐷 1 . If the element 𝑖 is assigned to an element 𝑗, we want to find 𝑊 such that 𝜓 𝑗 ≈ 𝑊 𝜑 𝑖 , and the order of the two streams is preserved. If we encode the assignments in a binary matrix 𝑌 , which must of course satisfy a number of constraints to preserve the temporal order, this can be written in matrix form as:

Ψ𝑌 ≈ 𝑊 Φ. The notations introduced here are illustrated in Fig. 5-2. The precise definition of the matrix 𝑌 will be provided in the following section.

Basic model

Let us begin by defining a binary assignment matrix 𝑌 in {0, 1} 𝐽×𝐼 . The entry 𝑌 𝑗𝑖 is equal to one if 𝑖 is assigned to 𝑗 and zero otherwise. For 𝑌 to encode a mapping, it must satisfy the constraint

∀𝑖, 𝐽 ∑ 𝑗=1 𝑌 𝑗𝑖 = 1, (5.1)
which implies that every element 𝑖 is assigned to exactly one element 𝑗.

Our main assumption is that the temporal ordering of the two modalities is preserved in the assignment. Therefore, if the element 𝑖 is assigned to 𝑗, then 𝑖 + 1 can only be assigned to 𝑗 ′ such that 𝑗 ′ ≥ 𝑗. Since we don't want to skip any element 𝑗, the map has to be subjective, and therefore 𝑖 + 1 can only be assigned to 𝑗 or 𝑗 + 1.

In the following, we will denote by 𝒴 the set of matrices 𝑌 that satisfy this property.

Given 𝑌 , Ψ𝑌 is a matrix whose 𝑖-th column is 𝜓 𝑗 if 𝑖 is mapped to 𝑗 in 𝑌 (Fig. 5-3). We then measure the discrepancy between Ψ𝑌 and 𝑊 Φ using the squared 𝐿 2 loss.

Using an 𝐿 2 regularizer for 𝑊 , our learning problem can be written as:

min 𝑌 ∈𝒴 min 𝑊 ∈R 𝐸×𝐷 1 2𝐼 ‖Ψ𝑌 -𝑊 Φ‖ 2 𝐹 + 𝜆 2 ‖𝑊 ‖ 2 𝐹 . (5.2)
When 𝑌 is fixed, this is a ridge regression problem; In particular, we can rewrite (5.2) as:

min 𝑌 ∈𝒴 𝑞(𝑌 ), (5.3)
where 𝑞 : 𝒴 → R is defined for all 𝑌 in 𝒴 by:

𝑞(𝑌 ) = min 𝑊 ∈R 𝐸×𝐷 [ 1 2𝐼 ‖Ψ𝑌 -𝑊 Φ‖ 2 𝐹 + 𝜆 2 ‖𝑊 ‖ 2 𝐹 ] .
(5.4)

The solution of ridge regression problem in Eq. ( 5.4) can be obtained in closed form as:

𝑊 * = Ψ𝑌 Φ ⊤ ( ΦΦ ⊤ + 𝐼𝜆Id 𝐷 ) -1 , (5.5)
where Id 𝑘 is the identity matrix in dimension 𝑘. Similar to DIFFRAC [START_REF] Bach | Diffrac: a discriminative and flexible framework for clustering[END_REF], substituting the optimal 𝑊 * in (5.4) yields:

𝑞(𝑌 ) = 1 2𝐼 Tr ( Ψ𝑌 𝑄𝑌 ⊤ Ψ ⊤ ) , (5.6)
where 𝑄 is a matrix depending on the data and the regularization parameter 𝜆:

𝑄 = Id 𝐼 -Φ ⊤ ( ΦΦ ⊤ + 𝐼𝜆Id 𝐷 ) -1 Φ.
(5.7)

Symbolic labels or continuous representations

The model presented here can be used in several ways. For example, we can use (5.8) the column order reflecting as before temporal order. Then the matrix Ψ can be constructed as the concatenation of the binary encodings of these classes. We have that 𝜓 𝑗 = 𝑒 𝑘 if and only if 𝑎 𝑗 = 𝑘 where 𝑒 𝑘 is the 𝑘-th vector of the canonical basis of dimension 𝐸. The product Ψ𝑌 corresponds to the assignment of elements in {1, . . . , 𝐼} to classes in {1, . . . , 𝐸}. This product Ψ𝑌 is exactly equal to (up to a transposition) the class indicator matrix 𝑍 in {0, 1} 𝐽×𝐸 as defined in [START_REF] Bojanowski | Weakly supervised action labeling in videos under ordering constraints[END_REF]. We illustrate the product Ψ𝑌 in when Ψ encode action labels in Fig. 5-3.

Ψ
The great advantage of the proposed model, as opposed to [START_REF] Bojanowski | Weakly supervised action labeling in videos under ordering constraints[END_REF], is that the data (Ψ) and the alignment variable (𝑌 ) are separate. This allows us to use representations for the data stream Ψ that are not necessarily binary. In that context, we can associate elements 𝑖 to time steps and elements 𝑗 to events. The dimension 𝐸 of the feature space of Ψ corresponds to action classes. The product Ψ𝑌 is equal to a class indicator matrix that assigns each frame to a given action class. The formulation presented in [START_REF] Bojanowski | Weakly supervised action labeling in videos under ordering constraints[END_REF] makes use of a matrix 𝑍 instead of representing separately Ψ and 𝑌 .

These could be for instance label embeddings, continuous word representations or bagof-words sentence representations. Moreover, this allows us to impose event-specific constraints on 𝑌 , which was impossible using the matrix 𝑍 = Ψ𝑌 .

The background class

We have assumed so far that each element 𝑖 maps onto one element 𝑗. However, in many cases, some (or even most) of the elements in {1, . . . , 𝐼} do not actually correspond to any element in {1, . . . , 𝐽}. For instance, if Φ is a sequence of video frames and Ψ encode a list of action labels, only some frames depict an action. The rest should be assigned to the background. This is implemented in [START_REF] Bojanowski | Weakly supervised action labeling in videos under ordering constraints[END_REF] by adding an explicit background class, and inserting columns in the matrix Ψ.

Suppose that there are 𝐸 classes of interest, the matrix Ψ is thus expanded as follows:

Ψ = ⎡ ⎣ 0 𝐸 𝜓 1 0 𝐸 𝜓 2 . . . 𝜓 𝐽 0 𝐸 1 0 1 0 . . . 0 1 ⎤ ⎦ .
(5.9)

In this presentation, we insert instead zero vectors of dimension 𝐸 in between the columns of Ψ:

Ψ = [ 0 𝐸 𝜓 1 0 𝐸 𝜓 2 . . . 𝜓 𝐽 0 𝐸 ] , (5.10)
and elements 𝑖 that are not assigned to a proper element 𝑗 are mapped onto 0 𝐸 . This has the advantage of not requiring an explicit background model (an additional row in 𝑊 ).

Affine maps and trivial solutions

As mentioned earlier, we parameterize the mapping between features as a linear one. Since we solve a regression problem, we actually want an affine one instead.

This can be done explicitly by adding a bias term 𝑏 in R 𝐸 and considering the map

Φ ↦ → 𝑊 Φ + 𝑏1 ⊤ 𝐼 .
In this work, we choose instead to add a constant row with entries equal to 𝑘 to the feature Φ:

Φ = ⎡ ⎣ Φ 𝑘1 ⊤ 𝐼 ⎤ ⎦ , (5.11)
and use a linear map defined as W = [𝑊, 1 𝑘 𝑏], which is a classical trick in machine learning [START_REF] Hastie | The Elements of Statistical Learning: Data Mining, Inference and Prediction[END_REF]. Doing so allows us to have a simpler presentation, simplifies the expressions and the corresponding implementation. Using these augmented variables, we have:

W Φ = 𝑊 Φ + 𝑏1 ⊤ 𝐼 .
(5.12)

The Frobenius norm regularizer is now equal to:

𝜆 2 ‖ W ‖ 2 𝐹 = 𝜆 2 ‖𝑊 ‖ 2 𝐹 + 𝜆 2𝑘 2 ‖𝑏‖ 2 2 .
(5.13) Using this augmented linear map is equivalent to using a regularized bias term, which is not desirable in regression problems [START_REF] Hastie | The Elements of Statistical Learning: Data Mining, Inference and Prediction[END_REF]. However, if we set the value of 𝑘 large compared to √ 𝜆, the bias become unregularized and we recover the classical formulation.

Discriminative clustering models are known to be plagued by trivial solutions [START_REF] Bach | Diffrac: a discriminative and flexible framework for clustering[END_REF][START_REF] Joulin | Discriminative Clustering for Image Co-segmentation[END_REF][START_REF] Bojanowski | Finding Actors and Actions in Movies[END_REF][START_REF] Grave | A convex relaxation for weakly supervised relation extraction[END_REF]. When an explicit bias term is used, the expression of 𝑄 contains centering matrices Π. Then it is easy to see that the constant vector 1 𝐼 is an eigenvector of 𝑄 associated with the eigenvalue 0. However, in our case, when we augment the features with a constant row, this is less clear. Let us define the augmented quadratic cost matrix Q as:

Q = Id 𝐼 -Φ⊤ ( Φ Φ⊤ + 𝐼𝜆Id 𝐷+1 ) -1 Φ.
(5.14)

The block matrix inversion formula can be used to show that 1 𝐼 is an eigenvector of Q associated with eigenvalue 0 as long as 𝑘 is sufficiently large (See Appendix A). In the rest of the presentation we drop the bar notation, but the reader should keep in mind that we augment the features with a constant row (with values typically around 10 4 ).

Multiple streams

Suppose now that we are given 𝑁 data streams (videos in our case), indexed by 𝑛 in {1, . . . , 𝑁 }. The approach proposed so far is easily generalized to this case by taking Ψ and Φ to be the horizontal concatenation of all the matrices Ψ 𝑛 and Φ 𝑛 corresponding to these streams:

Ψ = [Ψ 1 , . . . , Ψ 𝑁 ],
(5.15)

Φ = [Φ 1 , . . . , Φ 𝑁 ].
(5.16)

The matrices 𝑌 in 𝒴 have to be block-diagonal in this case, the diagonal blocks being the assignment matrices of every stream:

𝑌 = ⎡ ⎢ ⎢ ⎢ ⎣ 𝑌 1 0 . . . 0 𝑌 𝑁 ⎤ ⎥ ⎥ ⎥ ⎦
.

Using this parametrization we have:

‖Ψ𝑌 -𝑊 Φ‖ 2 𝐹 = 𝑁 ∑ 𝑛=1 ‖Ψ 𝑛 𝑌 𝑛 -𝑊 Φ 𝑛 ‖ 2 𝐹 , (5.17)
which is the desired sum of losses over the clips. This is the model actually used in our implementation.

Priors and constraints

As mentioned earlier, our formulation of alignment allows us to incorporate taskspecific knowledge in our model by adding constraints on the matrix 𝑌 . This allows us to avoid, for example, the degenerate solutions known to plague discriminative clustering [START_REF] Bach | Diffrac: a discriminative and flexible framework for clustering[END_REF][START_REF] Bojanowski | Weakly supervised action labeling in videos under ordering constraints[END_REF][START_REF] Guo | Convex Relaxations of Latent Variable Training[END_REF][START_REF] Joulin | Discriminative Clustering for Image Co-segmentation[END_REF]. Indeed, as discussed in Sec. 5.2.2, the constant vector 1 𝐼 is in the kernel of 𝑄. Let us consider an example: the (near) degenerate assignment matrix 𝑌 depicted in Fig. 5-4 (a) is very close to e 1 1 ⊤ 𝐼 . Therefore, the cost function associated with this assignment is close to zero. This motivates the use of priors and constraints that drive the assignment matrix away from this trivial solution.

In this section, we will propose two solutions. The first one consists in modeling the number of elements 𝑖 that should be assigned to element 𝑗. This leads to a quadratic cost in 𝑌 that we add to the optimization problem. The second solution corresponds to traditional constraints used when working with dynamic programming. Instead of using hard constraints, however, we propose to dualize them and include them as a linear penalization in our cost function.

Duration priors

Our formulation in terms of an assignment variable 𝑌 allows us to reason about the number of elements 𝑖 that are assigned to element 𝑗. In the context of text to video alignment, since each element 𝑖 is a video time interval, this number is the duration of text element 𝑗. More formally, the duration 𝛿(𝑗) of element 𝑗 is obtained as: 𝛿(𝑗) = e ⊤ 𝑗 𝑌 1 𝐼 , where e 𝑗 is the 𝑗-th vector of the canonical basis of R 𝐽 . Given a target duration 𝜇, we can penalize the squared deviation of 𝛿 from 𝜇. Assuming for simplicity a single variance parameter for all units, this leads to the following duration penalty: (5.18) This can be interpreted as having a Gaussian prior on the duration of each event.

𝑟(𝑌 ) = 1 2𝜎 2 ‖𝑌 1 𝐼 -𝜇‖ 2 2 .
Some heuristics for estimating suitable values of 𝜎 and the mean vector 𝜇 are needed.

In our experiments, we pick 𝜎 by validation and fix 𝜇 = 𝐼 𝐽 1 𝐽 . Given prior information on the duration of classes, more clever ways to estimate these parameters could be used. For instance, the mean and standard deviation of the duration of actions could be computed from an annotated action classification dataset.

Path priors

Some elements in 𝒴 correspond to very unlikely assignments. In speech processing and related tasks [START_REF] Rabiner | Fundamentals of speech recognition[END_REF], the warping paths are often constrained, forcing for example the path to fall in the Sakoe-Chiba band or in the Itakura parallelogram [START_REF] Sakoe | Dynamic programming algorithm optimization for spoken word recognition[END_REF]. Such constraints allow us to encode task-specific assumptions and to avoid degenerate solutions associated with the fact that constant vectors belong to the kernel of 𝑄. Band constraints, as illustrated in Fig. 5-4 (b), successfully exclude the kind of degenerate solutions presented in Fig. 5-4 (a).

Let us denote by 𝑌 𝑐 the band-diagonal matrix of width 𝛽, such that the diagonal entries are 0 and the others are 1; such a matrix is illustrated in Fig. 5-4 (b) in yellow.

In order to ensure that the assignment does not deviate too much from the diagonal, we can impose that at most 𝐶 non zero entries of 𝑌 are outside the band. We can formulate this constraint as:

Tr(𝑌 ⊤ 𝑐 𝑌 ) ≤ 𝐶.
This constraint could be added to the definition of the set 𝒴. However, doing so would prohibit a key step to our optimization algorithm, as described in Sec. 5.3. We therefore propose to add a penalization term to our cost function, corresponding to the Lagrange multiplier for this constraint. Indeed, for any value of 𝐶, there exists an 𝛼 such that, if we add to our cost function, the two solutions are equal, and thus the constraint is satisfied.

𝑙(𝑌 ) = 𝛼Tr(𝑌 ⊤ 𝑐 𝑌 ) (5.19)
The function 𝑙 is linear and adding it to our cost does not change the nature of our objective function. In practice, we select the value of 𝛼 by doing a grid search on a validation set. In the experimental section, we will evaluate the impact of the width of the band and of the parameter 𝛼 on the performance of our method.

Full problem formulation

Including the constraints defined in Sec. 5.2.3 into our objective function yields the following optimization problem: (5.20) where 𝑞, 𝑟 and 𝑙 are the three functions respectively defined in (5.6), (5.18) and (5.19). This is of course a difficult combinatorial optimization problem since the variables 𝑌 are binary and must satisfy complex constraints. In the following section we will describe the continuous and convex relaxation and the optimization algorithm that we use to obtain an approximate solution to this problem.

min 𝑌 ∈𝒴 𝑞(𝑌 ) + 𝑟(𝑌 ) + 𝑙(𝑌 ),

Optimization

Let us first describe how we relax the set of assignment matrices 𝒴. This relaxation transforms our problem into the minimization of a convex cost function over a convex domain. We then describe the Frank-Wolfe algorithm which efficiently solves the relaxed problem by exploiting the inherent structure of 𝒴. Finally, we discuss several rounding procedures which, given a solution to the relaxed problem, provide us with a feasible point of the initial problem.

Relaxation

Our problem, as formulated in Sec. 5.2.4, is the minimization of a quadratic function over a very large and discrete domain. It is quite easy to see that the set 𝒴 is composed of ( 𝐼-1

𝐽

) binary matrices: Indeed, the number of different assignment matrices corresponds to the different ways one can choose to "switch" from 𝑗 to 𝑗 + 1.

There are 𝐽 "switches" to choose amongst the 𝐼 -1 possible choices, hence the aforementioned cardinality.

We use a simple convex relaxation and replace the discrete set 𝒴 by its convex hull 𝒴. The set 𝒴 is a polytope that could be explicitly described by a polynomial number of linear inequalities. One advantage of the optimization algorithm proposed in the rest of this section is that it does not require having such an explicit description. Even though iterates will be inside the polytope, we don't need to know the parametrization of its facets.

Given an explicit description of 𝒴, our problem reduces to a classical quadratic program, that could in principle be solved using any off-the-shelf optimization toolboxes, provided that the quadratic cost matrix and the constraints fit in memory. We want to avoid using the explicit parametrization of the polytope as it involves a large amount of linear constraints and therefore long runtimes. Moreover, by writing our own solver, we manage to avoid storing the full 𝑄 matrix in memory. This can be problematic when the datasets get large (𝐼 typically of the order of 10 4 ). In the following section we describe the Frank-Wolfe algorithm which will allow us to minimize our cost over 𝒴 without access to its explicit description.

The Frank-Wolfe Algorithm

We want to minimize a convex function over a polytope 𝒴. This set is defined as the convex hull of a large but finite set of integer points exhibiting an alignment structure.

When it is possible to optimize a linear function over a constraint set of this kind, but other usual operations are not tractable, a good way to optimize a convex objective function is to use the iterative Frank-Wolfe algorithm (a.k.a. conditional gradient method) [Bertsekas, 1999, Frank and[START_REF] Frank | An algorithm for quadratic programming[END_REF]. We show in Sec. 5.3.3 that we can indeed minimize linear functions over 𝒴 efficiently, so this is an appropriate choice in our case.

In order to make notations simpler, let us just address in this section the problem of minimizing 𝑞 over 𝒴:

𝑞(𝑌 ) = 1 2𝐼 Tr(Ψ𝑌 𝑄𝑌 ⊤ Ψ ⊤ ), (5.21)
ignoring the two additional terms (𝑟 and 𝑙). The derivations including these two terms are very similar and only make notations more cumbersome.

The idea behind the Frank-Wolfe algorithm is rather simple. At every step 𝑘 of the algorithm, one computes an affine approximation 𝐿 𝑘 of the objective function 𝑞 at the current iterate 𝑌 𝑘 . In our case, this affine approximation has the following expression:

𝐿 𝑘 (𝑌 ) = Tr(𝑌 ∇ 𝑌 𝑞(𝑌 𝑘 )) -𝑞(𝑌 𝑘 ), (5.22)
where (5.24)

∇ 𝑌 𝑓 (𝑌 ) = 1 𝐼 𝑄𝑌 ⊤ Ψ ⊤ Ψ. ( 5
The constant term in Eq. (5.22) can be safely ignored in this optimization problem and we therefore focus on minimizing only the linear part. Finally, the iterate is updated as a convex combination of 𝑌 * and the current point 𝑌 𝑘 . This is repeated until convergence (see Alg. 1).

The interpolation parameter 𝛾 can be chosen either by using the universal step size 2 𝑘+1 , where 𝑘 is the iteration counter (see [START_REF] Jaggi | Revisiting Frank-Wolfe: Projection-free sparse convex optimization[END_REF] and references therein) or, in the case of quadratic functions, by solving a univariate quadratic equation. Let us define the Frank-Wolfe descent direction at step 𝑘 as 𝛿𝑌 𝑘 = 𝑌 * -𝑌 𝑘 . To find the optimal 𝛾, we solve the following problem: (5.25) which corresponds to performing an exact line search in the descent direction 𝛿𝑌 𝑘 .

min 𝛾∈R 𝑞(𝑌 𝑘 + 𝛾𝛿𝑌 𝑘 ),
Given our definition for 𝑞, this is equivalent to:

min 𝛾∈R Tr(Ψ𝑌 𝑘 𝑄𝑌 ⊤ 𝑘 Ψ + 2𝛾Ψ𝑌 𝑘 𝑄𝛿𝑌 ⊤ 𝑘 Ψ ⊤ + 𝛾 2 Ψ𝛿𝑌 𝑘 𝑄𝛿𝑌 ⊤ 𝑘 Ψ ⊤ ).
(5.26) This is a simple second order polynomial in 𝛾 and the optimal step size is:

𝛾 * = - Tr(Ψ 𝑌 𝑘 𝑄 𝛿𝑌 ⊤ 𝑘 Ψ ⊤ ) Tr(Ψ 𝛿𝑌 𝑘 𝑄 𝛿𝑌 ⊤ 𝑘 Ψ ⊤ )
.

(5.27)

Despite the minus sign, the value of 𝛾 * is actually positive, due to the definition of

𝛿𝑌 𝑘 .
A good feature of the Frank-Wolfe algorithm is that it provides a gap ∆ 𝑘 (referred to as the linearization duality gap [START_REF] Jaggi | Revisiting Frank-Wolfe: Projection-free sparse convex optimization[END_REF]) that can be used as a certificate of sub-optimality and stopping criterion. From now on, we just refer to it as a gap and ignore its dual interpretation. At iteration 𝑘, ∆ 𝑘 can be computed using the gradient and the descent direction as follows:

𝑘 ← 0 ∆ 0 ← ∞ while ∆ 𝑘 ≥ 𝜖 do Compute the current gradient in 𝑌 , ∇ 𝑌 𝑞(𝑌 𝑘 ) = 1 𝐼 𝑄𝑌 ⊤ 𝑘 Ψ ⊤ Ψ. Choose 𝑌 * in
∆ 𝑘 = 𝑞(𝑌 𝑘 ) -𝐿 𝑘 (𝑌 * ), = 1 𝐼 Tr(Ψ𝑌 𝑘 𝑄𝑌 ⊤ 𝑘 Ψ ⊤ ) - 1 𝐼 Tr(𝑌 * 𝑄𝑌 ⊤ 𝑘 Ψ ⊤ Ψ), = 1 𝐼 Tr((𝑌 𝑘 -𝑌 * )𝑄𝑌 ⊤ 𝑘 Ψ ⊤ Ψ), = -Tr(𝛿𝑌 𝑘 ∇ 𝑌 𝑞(𝑌 𝑘 )).
(5.28)

The complete optimization procedure is described in the special case of our relaxed problem in Algorithm 1. Figure 5-5 illustrates one step of the optimization and the computation of the gap is illustrated in Fig. 56.

Minimizing Linear Functions over 𝒵 by dynamic programming

The optimization algorithm described in the previous section requires us to minimize linear functions over the relaxed set 𝒴. It turns out to be easy to minimize such linear functions over the binary set 𝒴. A classical result in linear programming (see for instance Prop B.21 of [START_REF] Bertsekas | Nonlinear Programming[END_REF]) shows that the solution of a linear program over 𝒴 is also a solution over 𝒴. Intuitively, the solution over 𝒴 is either a vertex of the convex hull, or a whole face (including its vertices). Please note that this face can potentially be lower-dimensional (for instance, in R 3 , it could be an edge). In both

Figure 5-5 -Illustration of a Frank-Wolfe step (see [START_REF] Jaggi | Revisiting Frank-Wolfe: Projection-free sparse convex optimization[END_REF] for more details).

Left: the domain 𝒴 of interest, objective function (red), and its linearization at current point (blue). Right: top view of 𝒴. We show the plot of the function as well as the linearization 𝐿. The gap is computed as the difference between the current objective and the linearization at 𝑌 * . If the optimum is inside the set, the gap is equal to zero because the gradient is simply equal to zero. If the optimum is on a face of the polytope, the linearization has a constant value on the face.

cases, optimizing the same linear cost only over the vertices provides a valid solution over the convex hull. We will therefore focus on the minimization problem over 𝒴 and keep in mind that it also gives a solution over 𝒴 as required by the Frank-Wolfe algorithm.

Minimizing a linear function over 𝒴 amounts to solving the problem:

min 𝑌 ∈𝒴 Tr(𝐶 ⊤ 𝑌 ), (5.29)
where 𝐶 is a cost matrix in R 𝐼×𝐽 . This can be re-written as: (5.32)

We can think of 𝑃 * 𝑖𝑗 as the cost of the optimal path from (1, 1) to (𝑖, 𝑗) in the graph defined by admissible assignments. We have the following dynamic programming recursion:

𝑃 * 𝑖𝑗 = 𝐶 𝑖𝑗 + min(𝑃 * 𝑖-1 𝑗-1 , 𝑃 * 𝑖-1 𝑗 ).
(5.33)

The optimal value 𝑃 * 𝐼𝐽 can be computed in 𝑂(𝐼𝐽) time using dynamic programming, by incrementally computing the 𝑃 * 𝑖𝑗 values, and maintaining at each node (𝑖, 𝑗) back

Rounding in Ψ𝒴

We can also try to find the closest point in the space where the original leastsquares minimization is formulated. To this end we use a weighted euclidean distance, and solve the following problem: (5.35) which weighs the distances using the feature matrix Ψ. As before, expanding the norm gives:

min 𝑌 ∈𝒴 ‖Ψ(𝑌 -𝑌 * )‖ 2 𝐹 ,
‖Ψ(𝑌 -𝑌 * )‖ 2 𝐹 = Tr(Ψ𝑌 𝑌 ⊤ Ψ ⊤ ) + Tr(Ψ𝑌 * 𝑌 *⊤ Ψ ⊤ ) -2Tr(Ψ𝑌 * 𝑌 ⊤ Ψ ⊤ ).
(5.36)

This time, the first term is not constant. We observe that 𝑌 𝑌 ⊤ = Diag(𝑌 1 𝐼 ), where:

Diag : R 𝐽 → R 𝐽×𝐽 𝑣 ↦ → ⎡ ⎢ ⎢ ⎢ ⎣ 𝑣 1 0 . . . 0 𝑣 𝐽 ⎤ ⎥ ⎥ ⎥ ⎦
.

(5.37)

The 𝑗-th element of the diagonal counts how many elements 𝑖 were assigned to 𝑗. We have: (5.38) where:

Tr(Diag(𝑌 1)Ψ ⊤ Ψ) = Tr(1 ⊤ 𝐼 Y ⊤ Diag * (Ψ ⊤ Ψ)),
Diag * : R 𝐽×𝐽 → R 𝐽 𝐴 ↦ → ⎡ ⎢ ⎢ ⎢ ⎣ 𝐴 𝑖𝑖 . . . 𝐴 𝐽𝐽 ⎤ ⎥ ⎥ ⎥ ⎦ .
(5.39)

We can use the invariance of the trace under cyclic permutations and permute the matrices. A simple calculation then shows that the previous problem is equivalent to:

min 𝑌 ∈𝒴 Tr ( 𝑌 ⊤ ( Diag * (Ψ ⊤ Ψ)1 ⊤ 𝐼 -2Ψ ⊤ Ψ𝑌 * )) .
As before, this can be solved using dynamic programing.

Rounding in 𝑊

Our optimization procedure gives us two outputs, namely a relaxed assignment 𝑌 * ∈ 𝒴 and a model 𝑊 * in R 𝐸×𝐷 . We can use this model to predict an alignment 𝑌 in 𝒴 by solving the following quadratic optimization problem:

min 𝑌 ∈𝒴 ‖Ψ𝑌 -𝑊 * Φ‖ 2 𝐹 .
(5.40)

This rounding is interesting as it makes use of the actual cost function we optimize to choose a point in 𝒴. As before, by expanding the norm we observe that this is equivalent to a linear program. An important feature of this rounding procedure is that it can also be used on previously unseen data.

Semi-supervised setting

The proposed model is well suited to semi-supervised learning. Incorporating additional supervision just consists in constraining parts of the matrix 𝑌 . Let us assume that we are given a triplet (Ψ 𝑠 , Φ 𝑠 , 𝑌 𝑠 ) representing supervisory data. The rest of the data is denoted by (Ψ 𝑢 , Φ 𝑢 , 𝑌 𝑢 ). Using the additional data amounts to solving (5.20)

with matrices (Ψ, Φ, 𝑌 ) defined as: (5.41) where 𝜅 is a real weighting parameter.

Ψ = [Ψ 𝑢 , 𝜅 Ψ 𝑠 ], Φ = [Φ 𝑢 , 𝜅 Φ 𝑠 ], 𝑌 = ⎡ ⎣ 𝑌 𝑢 0 0 𝑌 𝑠 ⎤ ⎦ ,
Weighting the features this way corresponds to using the following loss:

‖Ψ𝑌 -𝑊 Φ‖ 2 𝐹 = ‖Ψ 𝑢 𝑌 𝑢 -𝑊 Φ 𝑢 ‖ 2 𝐹 + 𝜅 2 ‖Ψ 𝑠 𝑌 𝑠 -𝑊 Φ 𝑠 ‖ 2 𝐹 .
(5.42)

The parameter 𝜅 allows us to properly weigh the supervised and unsupervised data.

This can have a significant impact on the performance in practice. Since 𝑌 𝑠 is given, we can optimize over 𝒴 while constraining the lower right block of 𝑌 . As far as implementation is concerned, this means that we fix the lower-right entries in 𝑌 to the ground-truth values during optimization.

We have observed that manual annotations of videos are sometimes imprecise, or incoherent with the prediction of our method. In video for instance, our model, based on a discriminative cost, focuses on the most characteristic part of the action.

However, human annotators often deem the actions to last longer. In the case of drinking for example, annotations often also include pouring stuff in the glass as part of the action. Therefore, we propose to include these annotations in a soft manner instead.

As mentioned in Sec. 5.2, in order to model a "background class", odd columns in Ψ are filled with zeros. In the context of text to video alignment, this allows some video frames not to be assigned to any text. Instead of imposing that the assignment 𝑌 coincides with the ground-truth annotations, we constrain it to lie "within" annotated intervals. For any even (non null) element 𝑗, we force the set of video frames that are assigned to 𝑗 to be a subset of those in the ground truth interval. That way, we allow the assignment to pick the most discriminative parts of the video within the annotated interval. We illustrate these constraints in Fig. 567.

This way of incorporating supervision empirically yields much better performance.

We experimetnally demonstrate this improvement in Sec. 5.5.2.

Experimental evaluation

We first present some experiments on synthetic data in a controlled setup, and present them in Sec. 5.5.1. Doing so allows us to analyze the limitations of the model, with respect to various problem-dependent constants (such as 𝑇 , 𝐾 etc.). We then describe in Sec. 5.5.2 the dataset used for our real-world experiments with Hollywood movies. We evaluate how well our model labels videos and temporally localizes actions.

Finally, in Sec. 5.5.3, we present text-to-video alignment experiments where Ψ is a continuous text representation. We perform these experiments on a video dataset composed of cooking activities with textual annotations called TACoS [START_REF] Regneri | Grounding action descriptions in videos[END_REF].

Experimental Setup. The model described in this chapter does not include a training and testing phase per se. In order to carry out experiments in a proper fashion, we split datasets into three parts (Fig. 5678). In all our experiments we select these splits at random, using several random seeds in order to obtain confidence intervals. We denote these three splits as Sup (for supervised), Eval (for evaluation)

and Val (for validation). Sup is the part of data that has time-stamped annotations that are used in the semi-supervised setup. During the optimization, only a portion

Figure 5-8 -Illustration of our scheme for splitting the dataset for validation and evaluation. During optimization, our algorithm has access to the union of the three sets. When in the semi-supervised setup, ground-truth assignments are provided on a portion of the Sup set. Hyper parameters are chose based on the performance on the Val set and performance is reported on Eval. In our semi-supervised experiments we evaluate the performance of the method for different values of 𝑠.

𝑆 of the annotations of the Sup set is used. Val is the set of annotated examples on which we automatically adjust the hyper-parameters for our method (𝜆, 𝜎, 𝛼, 𝜅). In practice we fix the Val set to contain 5% of the clips in the dataset. All the numbers we provide are computed on the Eval set. We optimize our cost function over the union of all three sets, so samples from the Eval set (without the annotations) are visible during optimization. Please note that in any case, our method requires time-stamped annotations on a validation set in order to select hyper parameters.

Performance measure. We want to use a performance measure that quantifies the difference between a ground-truth assignment 𝑌 𝑔𝑡 , and the predicted one, 𝑌 * . Since we interleave background columns in Ψ, we only evaluate the even rows of 𝑌 * . For every such row 𝑗, we have a corresponding (prediction, ground-truth) interval pair that we will respectively denote 𝐺 * 𝑗 and 𝐺 𝑗 . We measure the assignment quality for each row by computing the following quantity: achieved when all actions are assigned to the correct annotations. However, accurate temporal segmentation is not required as long as the predicted bounds are within the ground truth interval. This measure is similar to the standard Jaccard measure used for comparing ensembles [START_REF] Jaccard | The distribution of the flora in the alpine zone[END_REF]. However, in the Jaccard measure, the denominator is |𝐺 𝑗 ∪ 𝐺 * 𝑗 |, therefore penalizing predictions that are too short, which is not desirable in our case.

|𝐺 𝑗 ∩ 𝐺 * 𝑗 | |𝐺 * 𝑗 | . ( 5

Controlled setup

In order to assess the performance of the proposed model when characteristics of the dataset vary, we perform some experiments on toy data. This allows us to control the length of both streams, the representation for both Φ and Ψ, and the ground-truth 𝑌 . Using this data, we will analyze the performance of the three proposed rounding schemes and the appearance of trivial solutions. But let us first describe the procedure in use to generate the synthetic dataset.

Dataset

In this section, we use a binary class encoding for the matrix Ψ and consider 𝐾 different classes. We pick at random using a uniform distribution the average duration for each of the 𝐾 classes and the length of the (𝐾 + 1)-th background class. Let us fix the number of clips to 𝑁 and for each clip 𝑛, uniformly select at random the length of the stream Ψ 𝑛 . Then, in order to build the stream, we select a sequence of integers in {1, . . . , 𝐾} by drawing them with replacement. Using the binary class representation, and interleaving background class in between columns, we obtain the matrix Ψ 𝑛 in {0, 1} 𝐾×𝐽𝑛 . For each of the 𝐽 𝑛 elements, we select a length using a gaussian distributions whose parameters were selected beforehand. That way, we build the ground-truth assignment matrix 𝑌 𝑛 .

Once these are computed, we pick a random map 𝑊 , by taking a matrix in R 𝐾×𝑑 with 𝑑 -1 columns filled with independent Gaussian noise and the last one filled with a constant. For each clip 𝑛, we obtain the feature representation Φ 𝑛 by solving the The performance of the three rounding schemes as a function of the noise 𝜎 in log scale is presented in Fig. 56789. The first obvious observation is that the performance of all three roundings degrades as the noise increases. There are three main regimes: absence of noise / a phase transition / very noisy features. When the noise is negligible, the solution obtained using the 𝑌 rounding performs close to perfection. The two other roundings have a slightly worse performance. The loss in performance is observed for streams that have the same element appearing multiple times in a row in Ψ. The Ψ𝑌 and the 𝑊 roundings cannot make a distinction between the two occurrences and elements of Φ are assigned to one of them arbitrarily.

When the noise increases, the 𝑌 rounding degrades very quickly while the two other ones keep a decent performance. As explained in Sec. 5.3.4, the three roundings proposed are arbitrary heuristic procedures. When inserting null columns in Ψ, we realize that the values of odd rows in 𝑌 do no change the objective. Performing the rounding using a euclidean distance in the space 𝒴 will select a binary 𝑌 while taking into account the values of odd rows of the relaxed solution. When rounding in Ψ𝑌 or 𝑊 , the influence of these rows is discarded, therefore focusing only on the rows of interest. This illustrates the fact that the 𝑌 rounding should not be used, as it happens in a space where the norm has no relation whatsoever with the cost function.

The best performing rounding procedure, for realistic noise ranges is the one in 𝑊 . This is expected as it is the only one that actually uses a cost which is tightly related to the objective function of our problem. As we will see it in the following section, it is also the rounding procedure which is most robust to the appearance of trivial solutions.

Trivial solutions

In the next experiment, in a controlled setup, we want to see how the trivial solutions appear. To this end, we run our algorithm on several variants of our toy Figure 5-10 -Evolution of the objective function and of the performance on the evaluation set as the length of stream Φ increases. We clearly see that the trivial solutions described in Sec. 5.2.2 take over when the average 𝐼 𝑛 increases. element (odd elements in the stream Ψ). However, for each clip 𝑛, we keep the same number of elements 𝐽 𝑛 (number of columns in Ψ). In order to make the problem nontrivial, we set the value of the noise parameter 𝜎 to 0.2.

In order to exhibit the appearance of these trivial solutions, we run the algorithm for various values of 𝐼. We show the evolution of the objective function and of the evaluation performance as the Φ stream gets longer. We plot these values as a function of the average stream length 1 𝑁 ∑ 𝑁 𝑛=1 𝐼 𝑛 in Fig. 5-10. We clearly see that as the length of the streams increases, both the performance and the objective drop. The evolution of the objective and how it decreases towards 0 indicates that the reason for this are the trivial solutions described before. Indeed, matrices 𝑌 with constant rows yield an objective value of 0. However, such matrices are not in the relaxed optimization domain 𝒴. As 𝐼 𝑛 gets larger, the set of matrices 𝒴 grows very quickly and gets closer to the aforementioned set of degenerate solutions.

Please note that this happens because these degenerate solutions yield a lower score than the actual ground truth assignment 𝑌 gt . This is the case only when the noise in the data is non-trivial and if the features are "perfect" (𝜎 = 0), we don't observe this drop. [START_REF] Bojanowski | Weakly supervised action labeling in videos under ordering constraints[END_REF] We evaluate the performance of our model on the data used in [START_REF] Bojanowski | Weakly supervised action labeling in videos under ordering constraints[END_REF]. It consists of videos annotated with a sequence of actions, where the precise temporal position of the actions is unknown. This has practical applications as providing precise temporal boundaries of actions in video is hard and time consuming.

Aligning sequences of actions

Using the proposed model, the annotator would only be asked to provide the sequence of actions that happens in the video. We first describe the dataset used in this experiment and the feature representation that we use. We then discuss the baselines to which we compare to and eventually present our results.

Dataset

Our input data consists of challenging video clips taken from feature movies that are annotated with sequences of actions. One possible source for such data is movies with their associated scripts [START_REF] Bojanowski | Finding Actors and Actions in Movies[END_REF][START_REF] Duchenne | Automatic annotation of human actions in video[END_REF][START_REF] Laptev | Learning realistic human actions from movies[END_REF], Sivic et al., 2009]. However, the annotations provided are noisy and do not provide ground-truth time-stamps for evaluation. To address this issue, we have constructed a new action dataset, containing clips explicitly annotated by sequences of actions. We have taken the 69 movies from which the clips of the Hollywood2 dataset were extracted [START_REF] Laptev | Learning realistic human actions from movies[END_REF], and manually added full time-stamped annotations for 16 action classes (12 of these classes are already present in Hollywood2). To build clips that form our input data, we search in the annotations for action chains containing at least two actions. To do so, we pad the temporal action annotations by 250 frames and search for overlapping intervals. A chain of such overlapping annotations forms one video clip with associated action sequence in our dataset. In the end we obtain 937 clips, with the number of actions ranging from 2 to 11. We subdivide each clip into temporal intervals of length 10 frames. Clips contain on average 84 intervals, the shortest containing 11, the longest 289.

Feature representation

We have to define a feature vector 𝜑 𝑖 for every interval 𝑖 of a video stream Φ. We split the video into 10 frames long intervals and represent this interval using a bagof-words vector 𝜑 𝑖 . To aggregate enough features, we decided to pool features from the 30-frame-long window centered on the interval. We compute video descriptors following [START_REF] Wang | Action Recognition with Improved Trajectories[END_REF], and generate a vocabulary of size 2000 for HOF features. We only use one channel to improve the running time, being aware that by doing so we sacrifice some performance. In our experiments, we also tried the MBH channels yielding very close performance. We use the Hellinger kernel as it has shown good performance for action recognition in the past. We do so by computing the explicit feature map: square-rooting the 𝑙 1 normalized histograms.

The label sequence provides a weak supervisory signal that can be used as our features Ψ. We consider a language composed of sixteen words, where every word corresponds to a label. Then, the representation 𝜓 𝑗 of every element 𝑗 is the indicator vector of the 𝑗-th label in the sequence. Since we do not model background, we simply interleave zero vectors in between meaningful elements.

Baselines

We compare the performance of our full model with some striped-down variants and several simple baselines. Given the very poor performance of the 𝑌 rounding, we don't report it in this experiment. However, for the two other roundings, we report the performance of both fixed and constrained semi-supervised models. As described in Sec. 5.4, the supervision available on the Sup set can be incorporated in two ways.

We also compare our model to a simple supervised square loss baseline (SL). For a given fraction 𝑆 of annotated data on the Sup set, we train the affine model using only the supervised data:

min 𝑊 1 2𝐼 𝑠 ‖Ψ 𝑠 𝑌 𝑠 -𝑊 Φ 𝑠 ‖ 2 𝐹 + 𝜆 2 ‖𝑊 ‖ 2 𝐹 .
(5.45)

Given the optimal map 𝑊 * we can get the corresponding integer assignment 𝑌 * using the same procedure as for the 𝑊 rounding. For this baseline, we compare two simple variants: as described in Sec. 5.2.2, we either explicitly model the background as in Eq. (5.9), or skip it as in Eq. (5.10). We refer to these two variants as respectively (SL with-back) and (SL no-back).

As a sanity check, we compare the performance of our algorithm to that of a random assignment that follows the priors. This random baseline obtains a performance measure of 32.8 with a standard error of 0.3.

Evaluating the assignment

We present the performance of our algorithm and the described baselines as a function of the amount of supervised data in Fig. 5-11. We run all methods for 10 different random splits and report the average performance and standard error. This experiment allows us to make several observations. First, the best performing rounding on this dataset is the one using the weighted norm (Ψ𝑌 ). This is not the same as what we observed on the synthetic and on the TACoS datasets.

Second, our semi-supervised model always works better than the supervised square loss baseline (SL). This shows that our weakly-supervised model is capable of making good use of the additional supervised data. The difference in performance between our best model and (SL no-back) is consistently better by at least 2% of performance measure. We can also notice that using only a small portion of supervised data (𝑆 = 0.1), our model performs as well as (SL no-back) with 𝑆 = 0.5.

Another interesting fact is the big difference in terms of performance between (SL no-back) and (SL with-back). We observe that for any amount of supervised data, not having an explicit model of the background works better. When the background is not modeled, the classes are better balanced, therefore avoiding scaling problems. janowski et al., 2014]. We observe that on this data, using the Ψ𝑌 rounding works better than using 𝑊 .

Ψ𝑌 roundings. However, even when fixing the assignment to the ground-truth we don't observe the drop at the beginning of the curve as in [START_REF] Bojanowski | Weakly supervised action labeling in videos under ordering constraints[END_REF]. This is probably due to the fact that we don't explicitly model the background class.

Text-to-video alignment

We also evaluate our method on the TACoS dataset [START_REF] Regneri | Grounding action descriptions in videos[END_REF]. This allows us to evaluate it on a corpus including actual natural language sentences. On this dataset, we use the 𝑊 rounding as it is the one that empirically gives the best test performance. We do not have yet a compelling explanation as to why this is the best performing one.

Dataset

The TACoS dataset is composed of 127 videos picturing people who perform cooking tasks. Every video is associated with two kinds of annotations. The first one is composed of low-level activity labels with precise temporal location. We do not make use of these fine-grained annotations in this work. The second one is a set of natural language descriptions that were obtained by crowd-sourcing. Annotators were asked to describe the content of the video using simple sentences. Each video Φ is associated with 𝑘 textual descriptions [Ψ 1 , . . . , Ψ 𝐾 ]. Every textual description is composed of multiple sentences with associated temporal extent. We consider as data points the pairs (Ψ 𝑘 , Φ) for 𝑘 in {1, . . . , 𝐾}.

Feature representation

We build the feature matrix Φ by computing dense trajectories [START_REF] Wang | Action Recognition with Improved Trajectories[END_REF]] on all videos. We compute dictionaries of 500 words for HOG, HOF and MBH channels. These experimentally provide satisfactory performance while staying relatively low dimensional. For a given temporal window, we concatenate bag-of-words representations for the four channels. As in the Hellinger kernel, we use the square root of 𝐿 1 normalized histograms as our final features. We use temporal windows of length 150 frames with a stride of 50.

To apply our method to textual data, we need to build a suitable feature representation Ψ for sentences. For every sentence in a textual description, we build a feature 𝜓 𝑖 . In our experiments, we explore multiple ways to represent sentences and empiri-cally compare their performance (Table 5.1). We discuss two ways to encode sentences into vector representations, one based on bag of words, the other on continuous word embeddings [START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF].

To build our bag-of-words representation, we construct a dictionary using all sentences in the TACoS dataset. We run a part-of-speech tagger and a dependency parser [Manning et al., 2014] in order to exploit the grammatical structure. These features are pooled using three different schemes. (1) ROOT: In this setup, we simply encode each sentence by its root verb as provided by the dependency parser. (2) ROOT+DOBJ: In this setup we encode a sentence by its root verb and its direct object dependency. This representation makes sense on the TACoS dataset as sentences are in general pretty simple. For example, the sentence "The man slices the cucumber" is represented by "slice" and "cucumber". (3) VNA: This representation is the closest to the usual bag-of-words text representation. We simply pool all the tokens whose part of speech is Verb, Noun or Adjective. The two first representations are very rudimentary versions of bags of words. They typically contain only one or two non zero elements.

We also explore the use of word embeddings [START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF], trained on three different corpora. First, we train them on the TACoS corpus. Even though the amount of data is very small (175,617 words), the vocabulary is also limited and the sentences are simple. Second, we train the vector representations on a dataset of 50,993 kitchen recipes, downloaded from allrecipes.com. This corresponds to a corpus of roughly 5 million tokens. However, the sentences are written in imperative mode, which differs from the sentences found in TACoS. For completeness, we also use the WaCky corpus [START_REF] Baroni | The wacky wide web: a collection of very large linguistically processed web-crawled corpora[END_REF], a large web-crawled dataset of news articles. We train representations of dimension 100 and 200. A sentence is then represented by the concatenation of the vector representations of its root verb and its root's direct object.

to retrain the representation on a text corpus that has similar distribution to the corpus of interest. Moreover, higher-dimensional representations (200) do not help probably because of the limited vocabulary size. The representations trained on a very large news corpus (UKWAC) benefits from using higher-dimensional vectors.

With such a big corpus, the representations of the cooking lexical field are probably merged together.

In Table . 5.2, we experimentally compare our approach to the baselines, in an unsupervised setting and a semi-supervised one. First, we observe that the diagonal baseline has reasonable performance. Note that this diagonal assignment is different from a random one since a uniform assignment between text and video in our context makes some sense. Second, we compare to the method of [START_REF] Bojanowski | Weakly supervised action labeling in videos under ordering constraints[END_REF] on ROOT, which is the only set up where this method can be used. This baseline is higher than the diagonal one but pretty far from the performances of our model using ROOT as well.

Using bag-of-words representations, we notice that simple pooling schemes work best. The best performing representation is purely based on verbs. This is probably due to the fact that richer representations can mislead such a weakly supervised method. As additional supervision becomes available, the ROOT+DOBJ pooling works much better that only using ROOT validating the previous claim.

Conclusion and discussion.

We presented a method able to align a video with its natural language description. We would like to extend our work to even more challenging scenarios including feature movies and more complicated grammatical structures. Also, our use of natural language processing tools is limited, and we plan to incorporate better grammatical reasoning in future work.

125

Chapter 6

Conclusion

We presented in this thesis two models that allow us to draw links between video and textual signal. The first one uses names of characters and verbs in the script to learn person and action models. Using names in scripts and character identification in video we provide a link between sentences in the script and tracks in the video. We evaluated the character identification model and showed that it improved over stateof-the-art methods at the time of publication while being a very flexible framework.

The action recognition performance was encouraging but low redundancy of verbs in movies made it hard to scale the method up. Simple improvements proposed in this thesis showed better performance and prove that the model is very flexible and that it is easy to incorporate such improvements.

A potential path for future work would be to scale this model up to many movies and many action classes. Even though the set of characters is specific to every movie, "action classes" or verbs, are shared. One could imagine training character models movie by movie and having a global action model that would be shared. However, this would probably generate optimization issues, as the number of samples to consider would grow linearly with the number of movies. The cost function that we proposed involved a quadratic program that might become intractable. Stochastic variants of the model could be considered, where the algorithm would not have access to all movies at the same time.

The second model allows to align sentences to a video stream by exploiting tem-poral ordering constraints. This alignment is recovered based on a joint model of video and text that we learn while finding the alignment. We have shown some experimental results on a dataset composed of cooking videos along with textual directions in the form of steps. While being quite challenging, the videos in this dataset were shot in a controlled environment. The model could also be applied to more complex datasources, for instance "do it yourself" cooking video found on the web.

The aforementioned temporal alignment model can also be used to align videos with action labels. The model automatically localizes the part of the video that corresponds to a given labels, therefore removing some annotation burden from the annotator. As argued in the introduction, providing precise temporal bounds to actions in video is very time consuming. Moreover, all annotators do not agree on the position of these bounds therefore creating annotations that are not all distributed the same way.

By using the kind of alignment models that we presented, the most discriminative portion of the video is selected, using the human annotation as weak supervision. An interesting extension of this work would be applying this kind of methods to modern, very large, action recognition datasets. Indeed, most of the videos found in these datasets contain a lot of noise and the video clips are not trimmed in a coherent way.

Both models try to establish a link between textual and video data. One of the golden goals of automatic video understanding is the automatic generation of textual descriptions of the scene pictured in the video. Recently published video captioning models show some promising results, opening up a new field of research. However, in order to properly describe the content of a video, one needs to properly understand the interactions between agents. Current video and image understanding models lack a proper representation of relations between objects and people.

As far as the formulations are concerned, all our models are based on linear classifiers and squared euclidian norm losses. These models could be made richer by considering a class of more complex classification functions and better losses. Standard, heuristic feature could be replace by learned representations based on deep learning.

Instead of learning a linear mapping on top of fixed video features, one could train the whole representation by back propagating the gradient.

Then we have that

𝐵 -1 Φ = ⎡ ⎣ 𝐴 -1 Φ + 𝑘 2 𝑢 𝐴 -1 Φ1 𝐼 1 ⊤ 𝐼 Φ ⊤ 𝐴 -1 Φ -𝑘 2 𝑢 𝐴 -1 Φ1 𝐼 1 ⊤ 𝐼 -𝑘 𝑢 1 ⊤ 𝐼 Φ ⊤ 𝐴 -1 Φ + 𝑘 𝑢 1 ⊤ ⎤ ⎦ ,
and

Φ⊤ 𝐵 -1 Φ = Φ ⊤ 𝐴 -1 Φ + 𝑘 2 𝑢 [Φ ⊤ 𝐴 -1 Φ11 ⊤ 𝐼 Φ ⊤ 𝐴 -1 Φ -Φ ⊤ 𝐴 -1 Φ1 𝐼 1 ⊤ 𝐼 -1 𝐼 1 ⊤ 𝐼 Φ ⊤ 𝐴 -1 Φ + 1 𝐼 1 ⊤ 𝐼 ].
If we write the scalar 𝑠 as 𝑠 = 1 ⊤ 𝐼 Φ ⊤ 𝐴 -1 Φ1 𝐼 , we compute:

Φ⊤ 𝐵 -1 Φ1 𝐼 = Φ ⊤ 𝐴 -1 Φ1 𝐼 + 𝑘 2 𝑢 [𝑠Φ ⊤ 𝐴 -1 Φ1 𝐼 -𝐼Φ ⊤ 𝐴 -1 Φ1 𝐼 -𝑠1 𝐼 + 𝐼1 𝐼 ],
which can be factorized as follows:

Φ⊤ 𝐵 -1 Φ1 𝐼 = Φ ⊤ 𝐴 -1 Φ1 𝐼 + 𝑘 2 (𝐼 -𝑠) 𝑢 [ 1 𝐼 -Φ ⊤ 𝐴 -1 Φ1 𝐼 ] .
We observe that we can factor out 𝑘 from the experssion of 𝑢:

𝑢 = 𝑘 2 ((1 + 𝜆 𝑘 2 )𝐼 -𝑠),
and then compute Q1 𝐼 as:

Q1 𝐼 = 1 𝐼 -Φ ⊤ 𝐴 -1 Φ1 𝐼 - 𝐼 -𝑠 𝐼 -𝑠 + 𝐼𝜆 𝑘 2 [ 1 𝐼 -Φ ⊤ 𝐴 -1 Φ1 𝐼 ] ,
which in turn can be simplified as:

Q1 𝐼 = 𝐼𝜆 𝑘 2 (𝐼 -𝑠) + 𝐼𝜆 [ 1 𝐼 -Φ ⊤ 𝐴 -1 Φ1 𝐼 ] .

Résumé

Abstract

Videos often depict complex scenes including people, objects and interactions between these and the enviorment.

Relations between agents are likely to evolve in time and agents can perform actions. The automatic understanding of video data is complicated as it requires to properly localize the agents both in space and time. Moreover, one need to automatically describe the relations between agents and how these evolve in time.

Modern approaches to computer vision heavily rely on supervised learning, where annotated samples are provided to the algorihtm to learn parametric models. However, for rich data such as video, the lableling process starts to be costly and complicated. Also, symbolic labels are not sufficient to encode the complex interactions between people, objects and scenes. Natural language offers much richer descriptive power and is thus a practical modality to annotated video data. Therefore, in this thesis we propose to focus on jointly modeling video and text. We explore such joint models in the context of movies with associated movie scripts, which provide accurate descriptions of the pictured events. The main challenge that we face is that movie scripts do not provide precise temporal and spatial localization of objects and actions.

We first present a model for automatically annotating person tracks in movies with person and action labels. The model uses a discriminative clustering cost function, and weak supervision in the form of constraints that we obtain from scripts. This approach allows us to spatially and temporaly localize agents and the actions they perform, as described in the script, in the video. However, the temporal and spatial localization is due to the use of person detection tracks. Then, in a second contribution, we describe a model for aligning sentences with frames of the video. The optimal temporal correspondance is again obtained using a discriminative model under temporal ordering constraints. This alignment model is applied on two datasets: one composed of videos associated with a stream of symbolic labels; a second one composed of videos with textual descriptions in the form of key steps towards a goal (cooking recipes for instance).

Keywords

computer vision, action recognition, video and text, weaklysupervised learning

Numéro national de thèse : xxxxx

  Figure 1-3 -Examples of annotated videos found in the Hollywood 2 action recognition dataset [Marszalek et al., 2009]. Every video is associated with a label, telling what action is performed in the given clip. We show examples for six out of the twelve manually defined classes in this dataset. Clips are taken from 69 Hollywood feature movies, providing a very challenging setup.

  latent support vector machine (L-SVM) framework with a potential function composed of several terms: an object class model, an attribute model, a class conditioned attribute model, an attribute coocurence term and a class-attribute coocurence term. When the latent variables are unknown in the training phase, the resulting optimization problem is non-convex. On the datasets used in the experiments, the attributes are available at training time but the authors show that using observed latent variables during training degrades the performance. The authors propose a non-convex cutting plane optimization algorithm and show experiments on two object-attribute datasets, demonstrating significant improvement over contemporary baselines.

  . In this work, videos are aligned to steps of the recipe based on the transcription of the speech signal. A hand-tuned HMM (transition parameters set by hand) is used to align the words of the transcript to steps of the recipe. This alignment is then further refined based on visual clues: the authors propose to train more than 2800 food detectors (including ingredients as well as full dishes) to refine the correspondence. The proposed method is used on a very large set of more than 180k videos automatically harvested from the web. As opposed to what we will present in Chapter 5, this does not involve training joint models. The described model relies on well suited heuristics and pre-trained representations (word embeddings and visual detectors).

  test-time performance of classification models, the authors propose to improve the temporal bounds of training video clips. A heuristic optimization algorithm based on a leave-on-out scheme is proposed. Supposing that there are 𝑁 video clips, classifiers are trained on 𝑁 -1 videos and all cropping of the remaining video are evaluated. Best performing cropping of a given length are selected for each video and the model is retrained on them. The authors show improved performance on several action classification dataset, showing that the proper localization of the action boundaries plays an important role. A more complex temporal model for actions is proposed in Niebles et al. [2010]. In order to better perform action classification, the authors propose a structured classification model. It is composed of 𝐾 different classifiers that have access to different portions of the video, at different scales. Their exact position is latent and the displacement with respect to an anchor position is penalized using a quadratic cost. The proposed formulation allows to train the parameters of each of the 𝐾 classifiers as well as the displacement penalties. Using this model allows to exploit temporal structure as these classifiers focus on different parts of the video. However, this publication remains unclear as to how to properly set the anchor points of these parts which seems like a critical part of the model.

  actom's location. A generative model of the actom's location and a discriminative model of each actom are learned on training data. The authors propose a dataset of videos annotated with temporally annotated actom's locations. The model is used to perform action detection and performance is compared to the detection results found in[START_REF] Duchenne | Automatic annotation of human actions in video[END_REF].[START_REF] Tang | Learning latent temporal structure for complex event detection[END_REF] propose to use a temporal model with latent classes to represent videos. The video is subdivided into short segments, and each such segment has an associated feature vector and a latent class. In order to cope with variable duration of latent classes, each segment is also associated with a duration variable. An energy for the whole model is defined using three potentials, depending on the features, latent and duration variables. The inference of hidden states can be carried out using dynamic programming. All model parameters are learnt on an action classification dataset, where each video is assigned to a binary action label. The optimization alternates between inferring the most likely hidden states and learning model. In the experimental section, the authors compare to[START_REF] Carlos Niebles | Modeling Temporal Structure of Decomposable Motion Segments for Activity Classification[END_REF] on two datasets, showing significantly better performance.

  The authors propose a joint spatio-temporal action recognition and localization in videos. Instead of using the whole video, including background, to prediction action classes, motion features are used arround a person detection. The model is formulated as a latent SVM model, with the location of "action bounding boxes" being latent. The model incorporate a unary term which measures if the given location is discriminative for the given class and a binary potential for smoothness of these locations in time. An efficient inference and learning algorithm is proposed but the model requires supervised bounding box locations at training time. The model is evaluated on the UCF-Sports dataset. This was further extended by Shapovalova et al. [2012], including a weakly-supervised model that could train without groudtruth bounding box locations for training.

  so on. The authors propose to annotate a video by considering the scenario as a set of constraints on the occurrence of primitives in time. An algorithm for transforming a scenario into what they call a constraint flow is proposed. Then, composite events can be recognized using a constrained optimization by dynamic programing. The authors demonstrate the performance of their algorithm on two datasets, one composed of surveillance videos and one on a Tennis video. Vahdat et al. [2013] propose a compositional model for event detection with latent temporal segment positions. The authors formulate the problem as a multiple kernel learning latent support vector machine, allowing to select discriminative portions of the video and to weight different feature channels in a principled manner. This allows to cope with temporal clutter, effectively ignoring noisy parts of the video (background). The authors demonstrated the performance of the proposed model on the TRECVID MED 11 dataset.

  presented in[START_REF] Vignesh Ramanathan | Linking people in videos with "their" names using coreference resolution[END_REF]. A discriminative clustering cost function based on the squared loss is used along with linear constraints to recognize characters in movies. The proposed improvements are two fold: first, additional equality constraints allowed to rule out a whole set of characters for large portions of the movie. Indeed, for a given scene in the movie, if a character is never mentionned in the script, the authors propose to set its latent class variable to zero. Moreover, the proposed approach includes a coreference resolution model, which allows to resolve who does the pronouns correspond to.[START_REF] Joulin | Efficient image and video co-localization with frank-wolfe algorithm[END_REF] propose a model for object co-localization, where occurences of the same object in different frames are localized. The cost function is again based on a squared loss and the authors propose some temporal constraints. The optimization is carried out using the Frank-Wolfe algorithm as in the contribution presented in Chapter 5. This allows the authors to exploit the structure of the temporal constraints that they propose, instead of using a classical quadratic problem solver.

Figure 4

 4 Figure 4-1 -Result of our automatic detection and identification of characters and their actions in the movie Casablanca. The automatically resolved correspondence between video and script is color-coded.

  min 𝑍∈𝒵, 𝑇 ∈𝒯 𝐷(𝑍, 𝑇 ) + 𝐺(𝑍, 𝑇 ), s.t. 𝐶(𝑍, 𝑇 ) ≤ 0, (4.1)

Figure 4

 4 Figure 4-2 -Illustration of the output of a Part-of-speech tagger (up) and a dependency tree parser (down). The part-of-speech tags are as follows: NNP -proper noun, RB -adverb, VBZ -verb in present tense, IN -preposition, DT -determiner, NNcommon noun. The dependencies are: nsubj -nominal subject, advmod -adverbial modifier, nmod -nominal modifier, case -case marking, det -determiner.

Figure 4 - 3 -

 43 Figure 4-3 -Representing video. Top: face track together with extracted facial features. Bottom: Motion features based on dense point trajectories extracted from tracked upper body bounding boxes.

Figure 4 - 7 -

 47 Figure 4-7 -Examples of automatically assigned names and actions in the movie Casablanca. Top row: Correct name and action assignments for tracks that have an character/action constraint in the script. Bottom row: Correct name and action assignments for tracks that do not have a corresponding constraint in the script, but are still correctly classified. Note that even very infrequent characters are correctly classified (Annina and Yvonne).

Figure 4

 4 Figure 4-8 -Evaluation of the two model improvements introduced in this thesis.

Figure 5

 5 Figure 5-2 -Illustration of the notations and model used in this chapter. The video features Φ are mapped to the same space as text features using the map 𝑊 . The temporal alignment of video and text features is encoded by the assignment matrix 𝑌 . Light blue entries in 𝑌 are zeros, dark blue entries are ones. See text for more details.

  to encode a sequence of action labels: Suppose that there are 𝐿 different action classes. Let us define the sequence of labels as an array 𝑎 of 𝐽 indices 𝑎 𝑗 in {1, . . . , 𝐿}: 𝑎 = [𝑎 1 , . . . , 𝑎 𝐽 ],

  Figure5-3 -Illustration of the Ψ matrix when aligning a sequence of action labels to a stream of video frames. In that context, we can associate elements 𝑖 to time steps and elements 𝑗 to events. The dimension 𝐸 of the feature space of Ψ corresponds to action classes. The product Ψ𝑌 is equal to a class indicator matrix that assigns each frame to a given action class. The formulation presented in[START_REF] Bojanowski | Weakly supervised action labeling in videos under ordering constraints[END_REF] makes use of a matrix 𝑍 instead of representing separately Ψ and 𝑌 .

Figure 5

 5 Figure 5-4 -(a) depicts a typical near degenerate solution where almost all the the elements 𝑖 are assigned to the first element, close to the constant vector element of the kernel of 𝑄. (b) Illustration of the constraint we propose. We want to force the alignment to stay outside of a given region (shown in yellow), which may be a band or a parallelogram. The dark blue entries correspond to the assignment matrix 𝑌 while the yellow ones represent the constraint set. See text for more details. (Best seen in color.)

  .23) 𝐿 𝑘 (𝑌 ) is minimized yielding a point 𝑌 * on the boundary of 𝒴: 𝑌 * ∈ arg min 𝑍∈𝒴 𝐿 𝑘 (𝑌 ).

  arg min 𝑌 ∈𝒴 Tr(𝑌 ∇ 𝑌 𝑞(𝑌 𝑘 )) using dynamic programming. Compute the Frank-Wolfe descent direction 𝛿𝑌 𝑘 . Compute the optimal Frank-Wolfe step size 𝛾 * . 𝑌 𝑘+1 ← 𝑌 𝑘 + 𝛾 * 𝛿𝑌 𝑘 ∆ 𝑘 ← -Tr(𝛿𝑌 𝑘 ∇ 𝑌 𝑓 (𝑌 𝑘 )). 𝑘 ← 𝑘 + 1. end Algorithm 1: The Frank-Wolfe optimization procedure.

Figure 5 - 6 -

 56 Figure 5-6 -Restriction of the function 𝑓 in the direction of the Frank-Wolfe descent.We show the plot of the function as well as the linearization 𝐿. The gap is computed as the difference between the current objective and the linearization at 𝑌 * . If the optimum is inside the set, the gap is equal to zero because the gradient is simply equal to zero. If the optimum is on a face of the polytope, the linearization has a constant value on the face.

𝑌

  𝑖𝑗 𝐶 𝑖𝑗 .(5.30) For each 𝑖, there is only one 𝑗 such that 𝑌 𝑖𝑗 is equal to one. Let us define a function 𝑚 : {1, . . . , 𝐼} → {1, . . . , 𝐽}, such that 𝑚(𝑖) = 𝑗 if 𝑌 𝑖𝑗 = 1. Because of the alignment structure of 𝑌 , if 𝑚(𝑖) = 𝑗, then 𝑚(𝑖 + 1) ∈ {𝑗, 𝑗 + 1}. Let us call ℳ 𝐼𝐽 , the set of such functions such that 𝑚(1) = 1 and 𝑚(𝐼) = 𝐽. Using this representation, the previous cost can be rewritten as: solved using dynamic time warping. Indeed, let us define for all 𝑖 ∈ {1, . . . , 𝐼} and 𝑗 ∈ {1, . . . , 𝐽}:

( a )

 a 𝑌 fixed to ground truth. (b) Corresponding constraints.

Figure 5 - 7 -

 57 Figure5-7 -Two ways of incorporating supervision. (a) the assignments are fixed to the ground truth: the dark blue entries exactly correspond to 𝑌 𝑠 , and golden entries are forbidden assignments; (b) the assignments are constrained. For even rows, assignments must be outside the golden strips. Light blue regions correspond to authorized paths for the assignment.

  dataset. The main parameters that we change are the lengths 𝐼 𝑛 of the streams Φ 𝑛 .In practice we change 𝐼 𝑛 by simply changing the average length of the background 115

Figure 5 -

 5 Figure5-11 -Evaluation of our model and supervised baselines on the data from[START_REF] Bojanowski | Weakly supervised action labeling in videos under ordering constraints[END_REF]. We observe that on this data, using the Ψ𝑌 rounding works better than using 𝑊 .

Figure 5 -

 5 Figure 5-12 -Evaluation of the priors we propose in this chapter. (a) We plot the performance of our model for various values of 𝜎. When 𝜎 is big, the prior has no effect. We see that there is a clear trade off and an optimal choice of 𝜎 yields better performance. (b) Performance as a function of 𝛼 and width of the band. The shown surface is interpolated to ease readability. (c) Performance for various values of 𝛼. This plot corresponds to the slice illustrated in (b) by the black plane.

  Les vidéos représentent des scènes complexes, comprenant des humains et des objets, illustrant les interactions entre ces derniers et leur enviorment. Les relations entre agents sont susceptibles d'évoluer dans le temps et les agents peuvent effectuer des "actions". La compréhension automatique des vidéos nécessite de correctement localiser les agents à la fois dans l'espace et dans le temps. De plus, il faut décrire les relations entre ces agents et leur evolution temporelle.La vision par ordinateur repose souvent sur l'apprentissage supervisé, où des échantillons ettiquetés permettent d'apprendre les parametres d'un modèle. Cependant, pour des données aussi riches que la vidéo, l'ettiquetage est coûteux et compliqué. Les étiquettes symboliques ne sont pas suffisament riches pour encoder les interactions entre personnes, objets et scènes. Le langage naturel offre une puissance descriptive qui en fait un modalité pratique pour annoter des données vidéo. Nous proposons de mettre l'accent sur la modélisation conjointe de vidéo et de texte. Nous explorons des modèles joints dans le contexte de films avec leurs scripts de tournage. Le principal défi auquel nous sommes confrontés est que les scripts de films ne fournissent pas de localisation spatiale et temporelle des objets et des actions.Nous présentons d'abord un modèle permettant d'associer automatiquement des étiquettes de personne et d'action aux detections de personnes dans les films. Le modèle utilise une fonction de coût de clustering discriminatif, et une supervision faible sous la forme de contraintes que nous obtenons à partir de scripts. Cette approche nous permet de localiser spatialement et temporelement les agents et les actions qu'ils effectuent dans la video, tel que décrit dans le script. Cependant, la localisation temporelle et spatiale est principalement due à l' utilisation de détections de personnes. Dans une seconde contribution, nous décrivons un modèle permettant d'aligner des phrases avec les images de la vidéo. La correspondance temporelle est obtenue en utilisant un modèle discriminatif sous contraintes d'ordre temporel. Ce modèle d'alignement est appliqué à deux ensembles de données : un composé de vidéos associées à un flux d'étiquettes ; un autre composé de vidéos et descriptions sous la forme d'étapes (recettes de cuisines par exemple).

	Mots Clés
	vision par ordinateur, reconnaissance d'actions, texte et vidéo, apprentissage faiblement supervisé

As usual, we actually want an affine map. We will provide more details bout that in Sec. 5.2.2. For the time being, please assume that a constant row is added to Φ.

Acknowledgments

I would like to thank my supervisors Jean Ponce, Cordelia Schmid, Ivan Laptev and Josef Sivic. They have been of greatest help, and have shown a lot of patience and understanding during these four years. A special thank goes to Francis Bach who was a great mentor and guide despite the fact that he wasn't a direct supervisor.

I would also like to express my gratitude to the people I collaborated with: Rémi Lajugie, Guillaume Seguin, Edouard Grave, Jean-Baptiste Alayrac, Sylvain Arlot and Phillippe Cuvillier. The countless discussions and tinkering have been at the core of our research activities and I hardly imagine completing this work without them.

I want to thank all the people at WILLOW and SIERRA for creating an amazing work environment. An exceptional thank goes to my officemates Senanayak Sesh Kumar Karri, Aymeric Dieuleveut and Augustin Lefebvre. The relaxed yet serious environment and casual discussions we had contributed a lot to this thesis.

Obvious credits got to my close friends and family, for their great informal help and understanding. Eventually, I would like to thank Rachel Fonck for the amazing amount of support and comprehension during these studious years. This work was supported in part by the ERC grant VideoWorld.

Experiments

In this section we experimentally demonstrate the benefits of the proposed approach. We first test the sensitivity to parameter choices in a controlled character identification setup. Second, we show that even for learning names alone (without actions), the proposed method outperforms other state-of-the-art weakly supervised learning techniques designed for the same task. Finally, we demonstrate benefits of learning names and actions jointly compared to resolving both tasks independently.

Learning names: controlled set-up

Here we assess the sensitivity of the proposed method to the following four important parameters: the number of bags |𝐼|, the number of classes 𝑃 , the number of samples per bag |𝒩 𝑖 | and the number of annotations per bag |Λ 𝑖 |. We will use real data -1,273 face tracks and their descriptors from the movie Casablanca -but group the tracks into bags in a controlled manner. Each track is labeled with a ground truth name from the set of 18 main characters (or other). To create each bag, we first sample a track from a uniform distribution over characters and then complete the bag with up to |𝒩 𝑖 | tracks by randomly sampling tracks according to the true distribution of the characters in the movie. Each bag is annotated according to the first sample.

Given this data, we solve the sub-problem related to faces, i.e., no joint action labels are used in this experiment.

As discussed in Section 4.2, each face track is assigned to a class by maximizing the rows of 𝑍. Following the work of [START_REF] Everingham | Hello! My name is... Buffy" -Automatic Naming of Characters in TV Video[END_REF], [START_REF] Sivic | Who are you?" -Learning person specific classifiers from video[END_REF] we measure performance by plotting a curve of per-sample accuracy vs. proportion of labeled tracks. Ideally, the accuracy would be one for all confidence values, but in practice the accuracy drops for samples with lower confidence. We illustrate results for different bag layouts in Figure 4-4.

Abstract

We present a discriminative model for aligning a video with its textual description. We propose to learn an affine map between the feature representation of the two modalities with a latent alignment. Using a square loss function allows us to invert the problem and obtain a cost that only depends on the alignment variable. The aforementioned map remains implicit and can be recovered at any time given the optimal correspondence. Our model is trained using an efficient algorithm which exploits the temporal structure of the problem. The performance of our approach is evaluated on three different datasets, allowing us to assess the importance of all our design choices. and frames. We propose a model that learns a mapping between video and textual features while finding the optimal correspondence. In our experiments we only use global sentence and frame representations. We do not try to spatially localize parts of the video that correspond to a given word. This chapter is structured as follows: In Sec. 5.2 we explain the problem setting and describe the proposed model. We also review the variable parametrization, the main cost function and additional priors that we propose. We present the proposed optimization algorithm in Sec. 5.3. That includes the convex relaxation, the Frank-Wolfe algorithm and the rounding procedure that we use. In Sec. 5.4 we briefly describe how we handle the use of additional supervised data. Finally, in Sec. 5.5 we present the empirical evaluation of the proposed model.

Introduction

Contributions. This chapter makes the following contributions: (i) We present a general model for aligning two streams of data, (ii) we propose a convex relaxation for our problem and an efficient algorithm to solve the relaxation, (iii) the performance of the proposed model is evaluated on three different dataset. We analyze the influence of our design choices on the final performance. This chapter is based on two previously published works: [START_REF] Bojanowski | Weakly supervised action labeling in videos under ordering constraints[END_REF] and [START_REF] Bojanowski | Weakly-supervised alignment of video with text[END_REF]]. Here we combine and extend the models found in these two publications. We also include additional evaluation with experiments carried out in a controlled setup on a toy dataset.

Proposed model

Problem statement and approach

Let us assume that we are given a data stream, associated with two modalities, represented by temporally ordered features 𝜑 𝑖 (𝑖 = 1, . . . , 𝐼) and 𝜓 𝑗 (𝑗 = 1, . . . , 𝐽) respectively. In both cases, the indices respect the temporal order, that is, 𝜑 𝑖 occurs before 𝜑 𝑖 ′ if 𝑖 < 𝑖 ′ and, likewise, 𝜓 𝑗 occurs before 𝜓 𝑗 ′ if 𝑗 < 𝑗 ′ . We also write more compactly Φ = [𝜑 1 , . . . , 𝜑 𝐼 ] and Ψ = [𝜓 1 , . . . , 𝜓 𝐽 ] where Φ and Ψ are respectively pointers to the the minimal neighbors. The actual solution is found by backtracking the solution from (𝐼, 𝐽).

Rounding

Solving the relaxed problem provides a continuous solution 𝑌 * in 𝒴 and a corresponding optimal linear map 𝑊 * . Our original problem is defined on 𝒴, and we thus need to round 𝑌 * . We propose three rounding procedures, two of them corresponding to Euclidean norm minimization problems and a third one using the map 𝑊 * . All three roundings boil down to solving a linear problem over 𝒴, which can be done once again using dynamic programming. Since there is no principled way to pick one of these procedures over the others, we conduct an empirical evaluation in Sec. 5.5 to assess their strengths and weaknesses.

Rounding in 𝒴

The simplest way to round 𝑌 * is to find the closest point 𝑌 according to the Euclidean distance in the space 𝒴. This can be written as the following optimization problem:

(5.34)

Since we have that:

The first two terms are constant and therefore this problem reduces to a linear program over 𝒴. As mentioned in the previous section, this can be solved efficiently using dynamic programming. Please note that the euclidean distance is not necessarily the most appropriate for this space. (5.44) and then adding Gaussian noise of variance 𝜎 to each of the Φ 𝑛 . Using this procedure to generate our toy dataset, we have data that corresponds to our model. This allows us to observe our model's inherent shortcomings. In our experiments, we will observe the evolution of performance as a function of the noise variance.

Roundings and noise

The first thing that we want to analyze on this synthetic data is the performance of the three proposed roundings. We propose to observe their performance as we change the amount of noise that we add to the features Φ. We split the dataset as described at the beginning of this section and pick hyper parameters on the validation set. In this experiment, we don't use any of the priors that we described so we only have to select 𝜆. All experiments are performed without supervision on the sup set (𝑆 = 0).

We run them for ten different random seeds and report the average performance along with the standard deviation.

Baselines

On this dataset, we considered two baselines. The first one is [START_REF] Bojanowski | Weakly supervised action labeling in videos under ordering constraints[END_REF] using the ROOT textual features. Verbs are used in place of labels by the method. The second one, that we call Diagonal, corresponds to the performance obtained by the uniform alignment. This corresponds to assigning the same amount of video elements 𝑖 to each textual element 𝑗.

Figure 5-13 -Representative qualitative results for our method applied on TACoS.

Correctly assigned frames are in green, incorect ones in red.

Evaluation of the priors

We propose in Sec. 5.2.3 two priors for including prior knowledge and avoiding degenerate solutions to our problem. In this section, we evaluate the performance of the two proposed priors on TACoS. To this end, we run our method with the two We see that both priors are useful. The duration prior, when 𝜎 is carefully chosen, allows us to improve performance from 0.441 (infinite 𝜎) to 0.475. There is a clear trade-off in this parameter. Using a bit of duration prior helps us to get a meaningful 𝑌 * by discarding degenerate solutions. However, when the prior is too strong, we obtain a degenerate solution with decreased performance.

The band prior (as depicted in Fig. 5-12, b andc) improves performance even more. We plot in (b) the performance as a joint function of the parameter 𝛼 and of the width of the band 𝛽. We see that the width that provides the best performance is 0.1. We plot in (c) the corresponding performance as a function of 𝛼. Using large values of 𝛼 corresponds to constraining the path to be entirely inside the band, which explain why the performance flattens for large 𝛼. When using a small width, the best path is not entirely inside the band and one has to carefully choose the parameter 𝛼.

We show in Fig. 5 Table 5.2 -Performance when no supervision is used to compute the assignment (nosup) and when half of the dataset is provided with time stamped sentences (semisup).

Appendix A

Zero eigenvalues of 𝑄

We want to show that 1 𝐼 is in the kernel of Q (eigenvector associated with eigenvalue 0). Let us use the augmented definition of Q and define 𝐵:

𝐵 can be expressed as:

Let us define:

then using the block matrix inversion formula, we can get an explicit expression for 𝐵 -1 :

where 𝑢 = (𝑘 2 + 𝜆)𝐼 -𝑘 2 1 ⊤ 𝐼 Φ ⊤ 𝐴 -1 Φ1 𝐼 .

Thus the result:

where 0 𝐼 is the zero vector in dimension 𝐼.

139