Une prévision correcte de la consommation d'électricité est fondamentale pour le bon fonctionnement du réseau électrique français, dont Réseau de Transport d'Electricité a la charge. Les prévisions utilisées quotidiennement par RTE sont issues d'un modèle alliant une régression paramétrique non linéaire et un modèle SARIMA.Dans l'idée d'obtenir un modèle de prévision adaptatif, des méthodes de prévision non-paramétriques ont déjà été testées sans succès véritable. On sait notamment que la qualité d'un prédicteur non-paramétrique résiste mal à un grand nombre de variables explicatives, ce qu'on appelle communément le fléau de la dimension.On a proposé récemment des méthodes semi-paramétriques d'estimation d'une régression qui améliorent l'approche non-paramétrique pure. L'une d'elles, basée sur la notion de ''directions révélatrices'' appellée MAVE (Moving Average -conditional- Variance Estimation), peut s'appliquer aux séries temporelles. Nous étudions empiriquement son efficacité pour prédire les valeurs futures d'une série temporelle autorégressive.Nous adaptons ensuite cette méthode, d'un point de vue pratique, pour prédire la consommation électrique. Nous proposons un modèle semi-paramétrique semi-linéaire, basé partiellement sur la méthode MAVE, qui permet de prendre en compte simultanément l'aspect autorégressif du problème, et l'introduction de variables exogènes. La procédure d'estimation proposée se révèle efficace en pratique.

L'objectif de cette thèse est de contribuer à l'élaboration de méthodes d'aide à la conception de systèmes coopératifs en prenant en compte les contraintes temporelles de manière quantitative. L'approche développée est fondée sur les réseaux de Petri, la logique linéaire et les graphes de contraintes temporelles. C'est une approche orientée « événements » et non orientée « états » comme c'est souvent le cas dans les approches fondées sur les réseaux de Petri. Elle est décomposée en deux étapes : une étape d'analyse « qualitative » et une étape d'analyse « quantitative ». La première consiste à obtenir les relations de causalité entre les événements appartenant à un scénario donné. L'équivalence entre un arbre de preuve en logique linéaire et le processus fini obtenu par dépliage d'un réseau de Petri à partir du même marquage initial montre que ces relations sont des relations de précédence. L'introduction de la notion de séquent caractéristique permet de mettre en Suvre une approche compositionnelle des processus à partir des règles du calcul des séquents. La deuxième étape consiste à passer du graphe décrivant les relations de précédence à un graphe de contraintes temporelles exprimant de façon linéaire l'ensemble des contraintes temporelles quantitatives que doivent vérifier les dates des franchissements des transitions dans un scénario. Il devient ainsi possible d'exploiter tous les résultats des techniques classiques d'analyse et de propagation de contraintes. Cette démarche est complètement cohérente avec les réseaux de Petri p-temporels mais difficilement compatible avec les t-temporels car ils engendrent des ensembles de contraintes qui sont plus complexes. Nous avons illustré cette démarche par un problème simple d'ordonnancement de documents multimédias. Nous avons par la suite montré comment, pour les réseaux de Petri t-temporels, nous pouvions calculer les dates de franchissements et les durées de séjour des jetons dans les places en restant sous une fo rme symbolique dans le cadre de la sémantique faible.

La thèse porte sur l'apport de la méthode de Laplace pour l'approximation du filtre bayésien dans des modèles de Markov cachés généraux, c'est-à-dire dans un cadre séquentiel, avec comme domaine d'application privilégié la poursuite de cibles mobiles. A la base, la méthode de Laplace est une méthode asymptotique pour le calcul d'intégrales, c'est-à-dire dans un cadre statique, valide en théorie dès que la fonction à intégrer présente un maximum de plus en plus significatif, lequel apporte la contribution essentielle au résultat. En pratique, cette méthode donne des résultats souvent très précis même en dehors de ce cadre de validité théorique. Les deux contributions principales de la thèse sont les suivantes. Premièrement, nous avons utilisé la méthode de Laplace en complément du filtrage particulaire : on sait en effet que les méthodes de Monte Carlo séquentielles basées sur l'échantillonnage pondéré sont mises en difficulté quand la fonction de pondération (ici la fonction de vraisemblance) est trop localisée, par exemple quand la variance du bruit d'observation est trop faible, or c'est précisément là le domaine où la méthode de Laplace est efficace et justifiée théoriquement, d'où l'idée naturelle de combiner les deux points de vue. Nous proposons ainsi un algorithme associant la méthode de Laplace et le filtrage particulaire, appelé le Laplace particle filter. Deuxièmement, nous avons analysé l'approximation du filtre bayésien grâce à la méthode de Laplace seulement (c'est-à-dire sans génération d'échantillons aléatoires) : il s'agit ici de contrôler la propagation de l'erreur d'approximation d'un pas de temps au pas de temps suivant, dans un cadre asymptotique approprié, par exemple quand le bruit d'observation tend vers zéro, ou quand le bruit d'état et le bruit d'observation tendent conjointement (et à la même vitesse) vers zéro, ou plus généralement quand l'information contenue dans le système tend vers l'infini, avec une interprétation en terme d'identifiabilité.

Face à l'explosion des nouvelles technologies (mobiles, capteurs, etc.), de grandes quantités de données localisées dans l'espace et dans le temps sont désormais disponibles. Les bases de données associées peuvent être qualifiées de bases de données spatio-temporelles car chaque donnée est décrite par une information spatiale (e.g. une ville, un quartier, une rivière, etc.) et temporelle (p. ex. la date d'un événement). Cette masse de données souvent hétérogènes et complexes génère ainsi de nouveaux besoins auxquels les méthodes d'extraction de connaissances doivent pouvoir répondre (e.g. suivre des phénomènes dans le temps et l'espace). De nombreux phénomènes avec des dynamiques complexes sont ainsi associés à des données spatio-temporelles. Par exemple, la dynamique d'une maladie infectieuse peut être décrite par les interactions entre les humains et le vecteur de transmission associé ainsi que par certains mécanismes spatio-temporels qui participent à son évolution. La modification de l'un des composants de ce système peut déclencher des variations dans les interactions entre les composants et finalement, faire évoluer le comportement global du système.Pour faire face à ces nouveaux enjeux, de nouveaux processus et méthodes doivent être développés afin d'exploiter au mieux l'ensemble des données disponibles. Tel est l'objectif de la fouille de données spatio-temporelles qui correspond à l'ensemble de techniques et méthodes qui permettent d'obtenir des connaissances utiles à partir de gros volumes de données spatio-temporelles. Cette thèse s'inscrit dans le cadre général de la fouille de données spatio-temporelles et l'extraction de motifs séquentiels. Plus précisément, deux méthodes génériques d'extraction de motifs sont proposées. La première permet d'extraire des motifs séquentiels incluant des caractéristiques spatiales. Dans la deuxième, nous proposons un nouveau type de motifs appelé "motifs spatio-séquentiels". Ce type de motifs permet d'étudier l'évolution d'un ensemble d'événements décrivant une zone et son entourage proche. Ces deux approches ont été testées sur deux jeux de données associées à des phénomènes spatio-temporels : la pollution des rivières en France et le suivi épidémiologique de la dengue en Nouvelle Calédonie. Par ailleurs, deux mesures de qualité ainsi qu'un prototype de visualisation de motifs sont été également proposés pour accompagner les experts dans la sélection des motifs d'intérêts.

Ce travail de thèse a eu pour objectif de définir et mettre en oeuvre l'architecture décisionnelle d'un robot réalisant une tâche en collaboration avec un homme pour atteindre un but commun. Un certain nombre de fonctionnalités existaient déjà ou ont été développées conjointement avec ce travail au sein de l'équipe. Ce travail a d'abord consisté en l'étude puis à la formalisation des différentes capacités nécessaires. Il s'est traduit concrètement par l'approfondissement de certains des modules fonctionnels existants par l'auteur ou par d'autres membres de l'équipe en lien étroit avec l'auteur. La première contribution principale de l'auteur a consisté à développer une couche de contrôle de haut niveau qui a permis l'intégration et la mise en oeuvre des différentes capacités du robot découpée en 3 activités : la construction et la mise à jour de l'état du monde ; la gestion des buts et des plans de haut niveau ; l'exécution et le suivi des mouvements de manipulation. La deuxième contribution principale a consisté à améliorer les raisonnement géométriques et temporelles pour d'abord permettre au robot de mieux suivre l'évolution de l'état du monde puis lui donner la capacité à inférer quand l'homme a des croyances distinctes de celle du robot.

Actuellement, des systèmes complets, contenant une partie logicielle et une partie matérielle, sont intégrés sur une même puce nommée Système-sur-Silicium (SoC). Pour faire face à la complexité d'intégration et maîtriser les contraintes, les équipes de recherche proposent de nouvelles méthodologies de conception qui reposent sur (1) la réutilisation de blocs logiciels ou matériels préconçus (Composant Virtuel VC, Intellectual Property IP), (2) sur l'élévation du niveau de description des applications (System-Level Design) et (3) sur l'orthogonalisation de différents aspects (fonctionnalité/architecture, calculs/communication, besoins/contraintes/choix d'implantation). Malheureusement la difficulté de réutilisation liée au niveau de description RTL (Register Transfer Level), auquel sont fournis les IPs, ne permet pas une intégration aisée et optimisée. Ainsi, les méthodologies d'intégration à base d'adaptateurs additionnels sont souvent inadaptées aux contraintes et à la spécificité des algorithmes utilisés dans le domaine du traitement du signal et de l'image (TDSI). Elles peuvent de ce fait aboutir à la violation des contraintes en terme de surface, consommation et performances du système. La synthèse de l'unité de traitement (UT) est réalisée à l'aide de l'outil GAUT (Générateur Automatique d'Unité de Traitement) dont l'ordonnancement est contraint par les paramètres temporel de l'intégrateur du composant virtuel. La synthèse de l'UT génère un ensemble de contraintes au E/S, modélisé sous la forme d'un IPERM (IP Execution Requirement Model). Ce dernier modélise (1) les dates de production et de consommation des données dans l'UT et (2) les bus sur lesquels elles transitent entre l'unité de communication et l'unité de traitement. Les modèles IPERM et IOCG sont finalement utilisés pour synthétiser l'unité de communication. Nous avons appliqué notre méthode à des algorithmes des domaines du TDSI et des Télécommunications. La première expérience est réalisée sur un exemple de Transformée de Fourrier Rapide (FFT). Pour les conditions d'expérimentation retenues, l'optimisation du nombre d'opérateurs est en moyenne de 20% et celle des registres de 7%, par rapport à une approche classique. La deuxième expérience utilise une Transformée en Cosinus Discrète (DCT) pour comparer les résultats, obtenus en appliquant l'approche d'intégration proposée dans ce manuscrit, avec les résultats des méthodes utilisant des adaptateurs. Pour l'exemple considéré, le gain sur les registres de communications varie de -2% à 88% à débit d'E/S constant. La dernière expérience, réalisée en partenariat industriel, démontre l'applicabilité de notre méthodologie sur un composant virtuel comportemental complexe (Maximum A Posteriori MAP) dans le contexte d'une application de Turbo décodage temps réel.<br /><br />Nous proposons dans ce mémoire une approche de réutilisation des IPs dans les applications orientées traitement du signal, de l'image et des télécommunications. Pour cela, nous basons notre approche sur la notion de composants virtuels de niveau algorithmique, définie dans le cadre des projets RNRT MILPAT (Méthodologie et Développement pour les Intellectual Properties pour Applications Telecom). Le flot de conception proposé s'inscrit dans la démarche Adéquation Algorithme Architecture du projet RNRT ALITPA (Définition et Application d'une méthodologie de développement pour les (IP) intellectual property de niveau comportemental dans les applications de télécommunication) et est basé sur l'utilisation de techniques de synthèse haut niveau sous contraintes d'intégration. Les unités fonctionnelles constituant l'architecture cible du composant sont (re)conçues en fonction des caractéristiques de l'architecture de communication du système et de la spécificité de l'application.<br /><br />Dans ce contexte, la spécification de l'IP est modélisée par un Graphe Flot de Signaux (SFG) qui, couplé aux temps de propagations des opérateurs et à la cadence d'itération, permet la génération d'un graphe de contrainte algorithmique ACG. Nous avons développé une d'analyse formelle des contraintes, qui repose sur les calculs de cycles, et permet de vérifier la cohérence entre la cadence, les dépendances de données de l'algorithme et les contraintes technologiques.<br /><br />Les contraintes d'intégration, spécifiées pour chacun des bus (ports) connectants l'IP aux autres composants du système, sont modélisées par un graphe de contraintes d'Entrée/Sortie IOCG (IO Constraint Graph) dont la sémantique est issue des travaux de Ku et De Micheli. Ce modèle supporte, entre autre, la modélisation (1) du type de transferts, (2) des varations temporelles des dates d'arrivées des données, (3) du séquencement des données échangées (4) des mécanismes liés aux protocoles. Les contraintes d'intégration et les contraintes algorithmiques de l'IP sont fusionnées pour fournir un graphe détaillé des contraintes GCG (Global Constraint Graph) exhibant les points de synchronisation entre l'environnement et le composant. Des optimisations pour l'implémentations sont proposées à partir de transformations formelles du graphe.<br /><br />La synthèse de l'unité de traitement (UT) est réalisée à l'aide de l'outil GAUT (Générateur Automatique d'Unité de Traitement) dont l'ordonnancement est contraint par les paramètres temporel de l'intégrateur du composant virtuel. La synthèse de l'UT génère un ensemble de contraintes au E/S, modélisé sous la forme d'un IPERM (IP Execution Requirement Model). Ce dernier modélise (1) les dates de production et de consommation des données dans l'UT et (2) les bus sur lesquels elles transitent entre l'unité de communication et l'unité de traitement. Les modèles IPERM et IOCG sont finalement utilisés pour synthétiser l'unité de communication.<br /><br />Nous avons appliqué notre méthode à des algorithmes des domaines du TDSI et des Télécommunications. La première expérience est réalisée sur un exemple de Transformée de Fourrier Rapide (FFT). Pour les conditions d'expérimentation retenues, l'optimisation du nombre d'opérateurs est en moyenne de 20% et celle des registres de 7%, par rapport à une approche classique. La deuxième expérience utilise une Transformée en Cosinus Discrète (DCT) pour comparer les résultats, obtenus en appliquant l'approche d'intégration proposée dans ce manuscrit, avec les résultats des méthodes utilisant des adaptateurs. Pour l'exemple considéré, le gain sur les registres de communications varie de -2% à 88% à débit d'E/S constant. La dernière expérience, réalisée en partenariat industriel, démontre l'applicabilité de notre méthodologie sur un composant virtuel comportemental complexe (Maximum A Posteriori MAP) dans le contexte d'une application de Turbo décodage temps réel.

Le Corbusier tente de ramener l’architecture à l’utilité et de créer une esthétique de pureté en parfaite harmonie avec celle-ci. Or s’il est conduit à s’opposer à tout excès et à économiser l’espace, ses choix esthétiques semblent mal répondre à cet impératif. Un seul superflu demeure un tabou chez lui: l’ornement. Le refus de cet ajout constitue ainsi un angle pour la compréhension du caractère de ses œuvres. Une enquête sur les causes de ce rejet mène à la conclusion que l’architecture nouvelle doit avoir comme principes l’esprit puriste, l’esprit scientifique déterministe et l’esprit individualiste. Pourtant, en même temps qu’elle les incarne, elle les enfreint systématiquement jusqu’à un certain point en vue de l’obtention des effets artistiques. De cette transgression de l’interdit résultent la réintroduction du superflu, une esthétique mi-authentique mi-inauthentique, et la qualification de l’espace de création corbuséen par la « parergonalité sans parergon ». Comme l’utilité ramenée en soi implique l’économie du temps, l’examen porte aussi sur les expériences temporelles que permet l’architecture nouvelle. Il montre qu’avec la « parergonalité sans parergon », celle-ci fait éprouver la décroissance du temps, sa suspension, son enchevêtrement avec l’objet, l’éternel présent présentiste, la logique de l’accroissement sous la logique de la réduction, des vécus semblables aux troubles de l’insomnie, etc. En même temps, cette architecture se remet en question, ouvrant ainsi d’autres historicités à l’art de bâtir et à l’homme, dont l’économie de l’espace ne valorise que le comportement corporel / Le Corbusier intends to bring architecture back to the utility and to create an aesthetics of purity in perfect harmony with this latter one. Yet if he is led to oppose all excess and to economize the space, his aesthetic choises do not seem to well respond to this imperative. One single surplus remains a taboo to him: the ornament. The opposition to this addition becomes then an angle for understanding the characteristic of his works. A conclusion of the inquiry into causes of this rejection is that the new architecture must hold the purist spirit, the scientific determinist spirit and the individualist spirit as principles. However, while embodying them actually, at the same time it infringes them systematically to a certain degree in order to create artistic effects. The outcomes of this transgression of the inhibited are the reintroduction of the surplus, a half authentic, half inauthentic aesthetics, and the characterization of Le Corbusier’s space of creation by “parergonality without parergon”. Since the utility brought back to itself implying the economy of time, we proceed as well to examine the temporal experiences made possible by the new architecture, and demonstrate that by means of the “parergonality without parergon”, it brings forth experiences like diminution of the time, its suspension, its entanglement with the object, the presentist eternal present, the logic of the increase under the logic of the reduction, effects similar to insomnia disorders, etc. Meanwhile, this architecture calls itself in question, opening then different historicities to architecture and to human being of which the economy of space values only the corporal movement

La définition d'une métrique entre des séries temporelles est un élément important pour de nombreuses tâches en analyse ou en fouille de données, tel que le clustering, la classification ou la prédiction. Les séries temporelles présentent naturellement différentes caractéristiques, que nous appelons modalités, sur lesquelles elles peuvent être comparées, comme leurs valeurs, leurs formes ou leurs contenus fréquentielles. Ces caractéristiques peuvent être exprimées avec des délais variables et à différentes granularités ou localisations temporelles - exprimées globalement ou localement. Combiner plusieurs modalités à plusieurs échelles pour apprendre une métrique adaptée est un challenge clé pour de nombreuses applications réelles impliquant des données temporelles. Cette thèse propose une approche pour l'Apprentissage d'une Métrique Multi-modal et Multi-scale (M2TML) en vue d'une classification robuste par plus proches voisins. La solution est basée sur la projection des paires de séries temporelles dans un espace de dissimilarités, dans lequel un processus d'optimisation à vaste marge est opéré pour apprendre la métrique. La solution M2TML est proposée à la fois dans le contexte linéaire et non-linéaire, et est étudiée pour différents types de régularisation. Une variante parcimonieuse et interprétable de la solution montre le potentiel de la métrique temporelle apprise à pouvoir localiser finement les modalités discriminantes, ainsi que leurs échelles temporelles en vue de la tâche d'analyse considérée. L'approche est testée sur un vaste nombre de 30 bases de données publiques et challenging, couvrant des images, traces, données ECG, qui sont linéairement ou non-linéairement séparables. Les expériences montrent l'efficacité et le potentiel de la méthode M2TML pour la classification de séries temporelles par plus proches voisins. / The definition of a metric between time series is inherent to several data analysis and mining tasks, including clustering, classification or forecasting. Time series data present naturally several characteristics, called modalities, covering their amplitude, behavior or frequential spectrum, that may be expressed with varying delays and at different temporal granularity and localization - exhibited globally or locally. Combining several modalities at multiple temporal scales to learn a holistic metric is a key challenge for many real temporal data applications. This PhD proposes a Multi-modal and Multi-scale Temporal Metric Learning (M2TML) approach for robust time series nearest neighbors classification. The solution is based on the embedding of pairs of time series into a pairwise dissimilarity space, in which a large margin optimization process is performed to learn the metric. The M2TML solution is proposed for both linear and non linear contexts, and is studied for different regularizers. A sparse and interpretable variant of the solution shows the ability of the learned temporal metric to localize accurately discriminative modalities as well as their temporal scales.A wide range of 30 public and challenging datasets, encompassing images, traces and ECG data, that are linearly or non linearly separable, are used to show the efficiency and the potential of M2TML for time series nearest neighbors classification.

Dans cette thèse, nous étudions des algorithmes pour le monitoring des traces d’activité à grande échelle. Le monitoring est une aptitude clé dans plusieurs domaines, permettant d’extraire de la valeur des données ou d’améliorer les performances d’un système. Nous explorons d’abord le monitoring de données temporelles. Nous présentons un nouveau type de jointure sur des intervalles, qui inclut des fonctions de score caractérisant le degré de satisfaction de prédicats temporels. Nous étudions ces jointures dans le contexte du batch processing (traitement par lots). Nous formalisons la Ranked Temporal Join (RTJ), une jointure qui combine des collections d’intervalles et retourne les k meilleurs résultats. Nous montrons comment exploiter les propriétés des prédicats temporels et de la sémantique de score associée afin de concevoir TKIJ , une méthode d’évaluation de requête distribuée basée sur Map-Reduce. Nos expériences sur des données synthétiques et réelles montrent que TKIJ est plus performant que les techniques de l’état de l’art et démontre de bonnes performances sur des requêtes RTJ n-aires sur des données temporelles. Nous proposons également une étude préliminaire afin d’étendre nos travaux sur TKIJ au domaine du stream processing (traitement de flots). Nous explorons ensuite le monitoring dans le crowdsourcing (production participative). Nous soutenons la nécessité d’intégrer la motivation des travailleurs dans le processus d’affectation des tâches. Nous proposons d’étudier une approche adaptative, qui évalue la motivation des travailleurs lors de l’exécution des tâches et l’exploite afin d’améliorer l’affectation de tâches qui est réalisée de manière itérative. Nous explorons une première variante nommée Individual Task Assignment (Ita), dans laquelle les tâches sont affectées individuellement, un travailleur à la fois. Nous modélisons Ita et montrons que ce problème est NP-Difficile. Nous proposons trois méthodes d’affectation de tâches qui poursuivent différents objectifs. Nos expériences en ligne étudient l’impact de chaque méthode sur la performance globale dans l’exécution de tâches. Nous observons que différentes stratégies sont dominantes sur les différentes dimensions de performance. En particulier, la méthode affectant des tâches aléatoires et correspondant aux intérêts d’un travailleur donne le meilleur flux d’exécution de tâches. La méthode affectant des tâches correspondant au compromis d’un travailleur entre diversité et niveau de rémunération des tâches donne le meilleur niveau de qualité. Nos expériences confirment l’utilité d’une affectation de tâches adaptative et tenant compte de la motivation. Nous étudions une deuxième variante nommée Holistic Task Assignment (Hta), où les tâches sont affectées à tous les travailleurs disponibles, de manière holistique. Nous modélisons Hta et montrons que ce problème est NP-Difficile et MaxSNP-Difficile. Nous développons des algorithmes d’approximation pour Hta. Nous menons des expériences sur des données synthétiques pour évaluer l’efficacité de nos algorithmes. Nous conduisons également des expériences en ligne et comparons notre approche avec d’autres stratégies non adaptatives. Nous observons que notre approche présente le meilleur compromis sur les différentes dimensions de performance. / In this thesis, we study scalable algorithms for monitoring activity traces. In several domains, monitoring is a key ability to extract value from data and improve a system. This thesis aims to design algorithms for monitoring two kinds of activity traces. First, we investigate temporal data monitoring. We introduce a new kind of interval join, that features scoring functions reflecting the degree of satisfaction of temporal predicates. We study these joins in the context of batch processing: we formalize Ranked Temporal Join (RTJ), that combine collections of intervals and return the k best results. We show how to exploit the nature of temporal predicates and the properties of their associated scored semantics to design TKIJ , an efficient query evaluation approach on a distributed Map-Reduce architecture. Our extensive experiments on synthetic and real datasets show that TKIJ outperforms state-of-the-art competitors and provides very good performance for n-ary RTJ queries on temporal data. We also propose a preliminary study to extend our work on TKIJ to stream processing. Second, we investigate monitoring in crowdsourcing. We advocate the need to incorporate motivation in task assignment. We propose to study an adaptive approach, that captures workers’ motivation during task completion and use it to revise task assignment accordingly across iterations. We study two variants of motivation-aware task assignment: Individual Task Assignment (Ita) and Holistic Task Assignment (Hta). First, we investigate Ita, where we assign tasks to workers individually, one worker at a time. We model Ita and show it is NP-Hard. We design three task assignment strategies that exploit various objectives. Our live experiments study the impact of each strategy on overall performance. We find that different strategies prevail for different performance dimensions. In particular, the strategy that assigns random and relevant tasks offers the best task throughput and the strategy that assigns tasks that best match a worker’s compromise between task diversity and task payment has the best outcome quality. Our experiments confirm the need for adaptive motivation-aware task assignment. Then, we study Hta, where we assign tasks to all available workers, holistically. We model Hta and show it is both NP-Hard and MaxSNP-Hard. We develop efficient approximation algorithms with provable guarantees. We conduct offline experiments to verify the efficiency of our algorithms. We also conduct online experiments with real workers and compare our approach with various non-adaptive assignment strategies. We find that our approach offers the best compromise between performance dimensions thereby assessing the need for adaptability.

La notion de métrique joue un rôle clef dans les problèmes d’apprentissage automatique tels que la classification, le clustering et le ranking. L’apprentissage à partir de données de métriques adaptées à une tâche spécifique a suscité un intérêt croissant ces dernières années. Ce domaine vise généralement à trouver les meilleurs paramètres pour une métrique donnée sous certaines contraintes imposées par les données. La métrique apprise est utilisée dans un algorithme d’apprentissage automatique dans le but d’améliorer sa performance. La plupart des méthodes d’apprentissage de métriques optimisent les paramètres d’une distance de Mahalanobis pour des vecteurs de features. Les méthodes actuelles de l’état de l’art arrivent à traiter des jeux de données de tailles significatives. En revanche, le sujet plus complexe des séries temporelles multivariées n’a reçu qu’une attention limitée, malgré l’omniprésence de ce type de données dans les applications réelles. Une importante partie de la recherche sur les séries temporelles est basée sur la dynamic time warping (DTW), qui détermine l’alignement optimal entre deux séries temporelles. L’état actuel de l’apprentissage de métriques souffre de certaines limitations. La plus importante est probablement le manque de garanties théoriques concernant la métrique apprise et sa performance pour la classification. La théorie des fonctions de similarité (ℰ , ϓ, T)-bonnes a été l’un des premiers résultats liant les propriétés d’une similarité à celles du classifieur qui l’utilise. Une deuxième limitation vient du fait que la plupart des méthodes imposent des propriétés de distance, qui sont coûteuses en terme de calcul et souvent non justifiées. Dans cette thèse, nous abordons les limitations précédentes à travers deux contributions principales. La première est un nouveau cadre général pour l’apprentissage conjoint d’une fonction de similarité et d’un classifieur linéaire. Cette formulation est inspirée de la théorie de similarités (ℰ , ϓ, τ) -bonnes, fournissant un lien entre la similarité et le classifieur linéaire. Elle est convexe pour une large gamme de fonctions de similarité et de régulariseurs. Nous dérivons deux bornes de généralisation équivalentes à travers les cadres de robustesse algorithmique et de convergence uniforme basée sur la complexité de Rademacher, prouvant les propriétés théoriques de notre formulation. Notre deuxième contribution est une méthode d’apprentissage de similarités basée sur DTW pour la classification de séries temporelles multivariées. Le problème est convexe et utilise la théorie des fonctions (ℰ , ϓ, T)-bonnes liant la performance de la métrique à celle du classifieur linéaire associé. A l’aide de la stabilité uniforme, nous prouvons la consistance de la similarité apprise conduisant à la dérivation d’une borne de généralisation. / The notion of metric plays a key role in machine learning problems, such as classification, clustering and ranking. Learning metrics from training data in order to make them adapted to the task at hand has attracted a growing interest in the past years. This research field, known as metric learning, usually aims at finding the best parameters for a given metric under some constraints from the data. The learned metric is used in a machine learning algorithm in hopes of improving performance. Most of the metric learning algorithms focus on learning the parameters of Mahalanobis distances for feature vectors. Current state of the art methods scale well for datasets of significant size. On the other hand, the more complex topic of multivariate time series has received only limited attention, despite the omnipresence of this type of data in applications. An important part of the research on time series is based on the dynamic time warping (DTW) computing the optimal alignment between two time series. The current state of metric learning suffers from some significant limitations which we aim to address in this thesis. The most important one is probably the lack of theoretical guarantees for the learned metric and its performance for classification.The theory of (ℰ , ϓ, τ)-good similarity functions has been one of the first results relating the properties of a similarity to its classification performance. A second limitation in metric learning comes from the fact that most methods work with metrics that enforce distance properties, which are computationally expensive and often not justified. In this thesis, we address these limitations through two main contributions. The first one is a novel general framework for jointly learning a similarity function and a linear classifier. This formulation is inspired from the (ℰ , ϓ, τ)-good theory, providing a link between the similarity and the linear classifier. It is also convex for a broad range of similarity functions and regularizers. We derive two equivalent generalization bounds through the frameworks of algorithmic robustness and uniform convergence using the Rademacher complexity, proving the good theoretical properties of our framework. Our second contribution is a method for learning similarity functions based on DTW for multivariate time series classification. The formulation is convex and makes use of the(ℰ , ϓ, τ)-good framework for relating the performance of the metric to that of its associated linear classifier. Using uniform stability arguments, we prove the consistency of the learned similarity leading to the derivation of a generalization bound.