Dissertations / Theses on the topic 'Réseaux de Graphes avec Attention'

La congestion routière constitue un défi majeur pour les zones urbaines, car le volume de véhicules continue de croître plus rapidement que la capacité globale du réseau routier. Cette croissance a des répercussions sur l'activité économique, la durabilité environnementale et la qualité de vie. Bien que des stratégies visant à atténuer la congestion routière ont connu des améliorations au cours des dernières décennies, de nombreux pays ont encore du mal à la gérer efficacement.Divers modèles ont été développés pour aborder ce problème. Cependant, les approches existantes peinent souvent à fournir des prédictions en temps réel et localisées qui peuvent s'adapter à des conditions de trafic complexes et dynamiques. La plupart de ces approches s'appuient sur des horizons de prédiction fixes et manquent de l'infrastructure intelligente nécessaire à la flexibilité. Cette thèse comble ces lacunes en proposant une approche intelligente, décentralisée et basée sur l'infrastructure pour l'estimation et la prédiction de la congestion routière.Nous commençons par étudier l'Estimation du Trafic. Nous examinons les mesures de congestion possibles et les sources de données requises pour différents contextes pouvant être étudiés. Nous établissons une relation tridimensionnelle entre ces axes. Un système de recommandation basé sur des règles est développé pour aider les chercheurs et les opérateurs du trafic à choisir les mesures de congestion les plus appropriées en fonction du contexte étudié.Nous passons ensuite à la Prédiction du Trafic, où nous introduisons notre approche DECOTRIVMS. Cette dernière utilise des panneaux intelligents à messages variables pour collecter des données detrafic en temps réel et fournir des prédictions à court terme avec des horizons de prédiction variables.Nous avons utilisé des Réseaux de Graphes avec Attention en raison de leur capacité à capturer des relations complexes et à gérer des données structurées en graphes. Ils sont bien adaptés pour modéliser les interactions entre différents segments routiers étudiés.Nous avons aussi employé des méthodes d'apprentissage en ligne, spécifiquement la Descente de Gradient Stochastique et la Descente de Gradient Adaptative. Bien que ces méthodes ont été utilisées avec succès dans divers autres domaines, leur application à la prédiction de la congestion routière reste sous-explorée. Dans notre thèse, nous visons à combler cette lacune en explorant leur efficacité dans le contexte de la prédiction de la congestion routière en temps réel.Enfin, nous validons l'efficacité de notre approche à travers deux études de cas réalisées à Mascate, Oman, et à Rouen, France. Une analyse comparative est effectuée, évaluant divers modèles de prédiction, y compris les Réseaux de Graphes avec Attention, les Réseaux de Graphes Convolutionnels et des méthodes d'apprentissage en ligne. Les résultats obtenus soulignent le potentiel de DECOTRIVMS, démontrant son efficacité pour une prédiction précise et efficace de la congestion routière dans divers contextes urbains
Traffic congestion presents a critical challenge to urban areas, as the volume of vehicles continues to grow faster than the system’s overall capacity. This growth impacts economic activity, environmental sustainability, and overall quality of life. Although strategies for mitigating traffic congestion have seen improvements over the past few decades, many cities still struggle to manage it effectively. While various models have been developed to tackle this issue, existing approaches often fall short in providing real-time, localized predictions that can adapt to complex and dynamic traffic conditions. Most rely on fixed prediction horizons and lack the intelligent infrastructure needed for flexibility. This thesis addresses these gaps by proposing an intelligent, decentralized, infrastructure-based approach for traffic congestion estimation and prediction.We start by studying Traffic Estimation. We examine the possible congestion measures and data sources required for different contexts that may be studied. We establish a three-dimensional relationship between these axes. A rule-based system is developed to assist researchers and traffic operators in recommending the most appropriate congestion measures based on the specific context under study. We then proceed to Traffic Prediction, introducing our DECentralized COngestion esTimation and pRediction model using Intelligent Variable Message Signs (DECOTRIVMS). This infrastructure-based model employs intelligent Variable Message Signs (VMSs) to collect real-time traffic data and provide short-term congestion predictions with variable prediction horizons.We use Graph Attention Networks (GATs) due to their ability to capture complex relationships and handle graph-structured data. They are well-suited for modeling interactions between different road segments. In addition to GATs, we employ online learning methods, specifically, Stochastic Gradient Descent (SGD) and ADAptive GRAdient Descent (ADAGRAD). While these methods have been successfully used in various other domains, their application in traffic congestion prediction remains under-explored. In our thesis, we aim to bridge that gap by exploring their effectiveness within the context of real-time traffic congestion forecasting.Finally, we validate our model’s effectiveness through two case studies conducted in Muscat, Oman, and Rouen, France. A comprehensive comparative analysis is performed, evaluating various prediction techniques, including GATs, Graph Convolutional Networks (GCNs), SGD and ADAGRAD. The achieved results underscore the potential of DECOTRIVMS, demonstrating its potential for accurate and effective traffic congestion prediction across diverse urban contexts

Nous étudions le problème de la conception de réseaux de télécommunications multiprotocoles tenant compte du phénomène d'encaspulation des données. Connaissant la structure en couches d'un réseau multiprotocoles et un ensemble de demandes devant être acheminées sur ce réseau, le problème de la conception de réseau consiste à choisir la capacité de chaque liaison parmi un ensemble de valeurs discrètes de telle sorte que le coût global du réseau soit le plus faible possible, tout en s'assurant que les demandes sont satisfaites. Nous scindons ce problème en deux sous-problèmes inter-dépendants : le problème de la réalisabilité d'un ensemble de capacités en regard d'un multiflot, qui peut être formulé comme un programe linéaire en variables inconnues, et le problème du dimensionnement de ces capacités, formulé comme un programme linéaire en variables bolléennes. Dans le cadre des réseaux multiprotocoles, le problème de la réalisabilité d'un ensemble de capacités en regard d'un multiflot fait intervenir la notion d'en-tête liée au phénomène d'encaspulation, ce qui rend sa résolution difficile. Nous introduisons dans cette thèse un modèle de multiflot dit non conservatif, et définissons la notion de pile de chemins. Nous étudions la complexité du problème de la recherche de piles de chemins comportant un nombre minimum de changements de protocoles dans les réseaux en couches. Nous donnons aussi un ensemble d'heuritiques pour la génération de piles de chemins de coût réduit négatif afin de résoudre le problème de réalisibilité. Le problème de dimensionnement des capacités peut être entièrement résolu de manière itérative en employant la classe des inégalités métriques. Par ailleurs, la formulation de ce problème faisant intervenir uniquement des variables booléennes, nous faisons appel à la technique dite lift-and-project due aux travaux de Lovasz et Schrijver sur le cône des matrices semi-définies positives, ainsi qu'aux travaux de Balas, Ceria, Cornuejols sur le rôle des contraintes disjonctives pour la résolution de programmes en variables booléennes. Nous étudions chacune de ces approches et donnons deux algorithmes de coupes polyédrales basés sur l'utilisation des opérateurs de projection définis par Lovasz et Schrijver d'une part, et Balas, Ceria, Cornuejols. Enfin nous donnons une méthode permettant de créer plusieurs relaxations semi-définies d'un programme linéaire en variables booléennes général, et nous appliquons une méthode au problème de dimensionnement des capacités. Des tests numériques permettent de dire que les solutions obtenues par cette méthode sont meilleures que celles obtenues par la simple relaxation linéaire de ce problème

Ce mémoire est consacré à la parallélisation d'un algorithme d'assemblage d'ADN de type de novo sur différentes plateformes matérielles, soit les processeurs multicoeurs et les accélérateurs de type FPGA. Plus précisément, le langage OpenCL est utilisé pour accélérer l'algorithme dont il est question, et de permettre un comparatif direct entre les les plateformes. Cet algorithme est d'abord introduit, puis son implémentation originale, développée pour une exécution sur une grappe de noeuds, est discutée. Les modifications apportées à l'algorithme dans le but de faciliter la parallélisation sont ensuite divulgées. Ensuite, le coeur du travail est présenté, soit la programmation utilisant OpenCL. Finalement, les résultats sont présentés et discutés.

L'émergence du Web 2. 0 a vu apparaître une grande quantité de données qui peuvent naturellement se représenter sous forme de graphes complexes. Plusieurs tâches d'analyse, de prédiction et de recherche d'informations ont pour objet ces données, alors que les modèles de l'état de l'art ne sont pas adaptés à ce type d'information. Dans cette thèse, nous nous intéressons à la problématique de classification/étiquetage automatique de noeuds dans des réseaux de contenu partiellement étiquetés et complexes. Cette tâche générique trouve de nombreuses applications par exemple pour l'annotation de photos/vidéos dans les réseaux sociaux, la détection du spam sur le Web ou bien l'étiquetage de grands réseaux d'utilisateurs. L'originalité de notre travail est de se focaliser sur deux types particuliers de réseaux peu abordés dans la littérature: les graphes multi-relationnels composés de plusieurs types de relation, et les graphes hétérogènes, composés de plusieurs types de noeud, et donc de plusieurs problématiques conjointes d'étiquetage. Dans un premier temps nous avons proposé deux nouveaux algorithmes pour l'étiquetage dans les graphes multi-relationnels. Ces algorithmes apprennent à pondérer les différents types de relation dans le processus de propagation des étiquettes selon leur utilité pour la tâche visée. Ils permettent d'apprendre à combiner les différents types de relation de manière optimale pour la classification, tout en utilisant l'information de contenu des noeuds. Dans un second temps, nous proposons un algorithme pour l'étiquetage dans les graphes hétérogènes. Ici, une difficulté particulière demeure dans le fait que chaque type de noeud possède son propre jeu d'étiquettes: par exemple des tags visuels pour une photo et des groupes pour un utilisateur, et qu'il faut donc résoudre ces différents problèmes de classification simultanément en s'aidant de la structure du graphe. Notre algorithme est basé sur l'utilisation d'une représentation latente commune à tous les types de noeud permettant de traiter les différents types de noeud de manière uniformisée. Les résultats expérimentaux montrent que ce modèle est capable de prendre en compte les corrélations entre les étiquettes de noeuds de type différent
The emergence of the Web 2. 0 has seen the apparition of a large quantity of data that can easily be represented as complex graphs. There is many tasks of information analysis, prediction and retrieval on these data, while the state-of-the-art models are not adapted. In this thesis, we consider the task of node classification/labeling in complex partially labeled content networks. The applications for this task are for instance video/photo annotation in the Web 2. 0 websites, web spam detection or user labeling in social networks. The originality of our work is that we focus on two types of complex networks rarely considered in existing works: \textbf{multi-relationnal graphs} composed of multiple relation types and \textbf{heterogeneous networks} composed of multiple node types then of multiple joint labeling problems. First, we proposed two new algorithms for multi-relationnal graph labeling. These algorithms learn to weight the different relation types in the label propagation process according to their usefullness for the labeling task. They learn to combine the different relation types in an optimal manner for classification, while using the node content information. Then, we proposed an algorithm for heterogeneous graph labeling. Here, a specific problem is that each type of node has it own label set: for instance visual tags for a photo and groups for an user, then we must solve these different classification problems simultaneously using the graph structure. Our algorithm is based on the usage of a latent representation common to all node types allowing to process the different node types in an uniformized manner. Our experimental results show that this model is able to take in account the correlations between labels of different node types

Nous présentons dans cette thèse une étude sur des algorithmes distribués asynchrones et déterministes de contrôle. Un système distribué consiste en un réseau de sites (processeurs, ordinateurs ou réseaux locaux). Dans cette thèse, nous ne considérons que des réseaux de sites communicants n'ayant ni mémoire partagée, ni horloge globale. De nombreux problèmes de l'algorithmique distribuée sont réductibles à la construction d'un arbre couvrant qui est la structure de contrôle qui nous intéresse. Nous étudions deux types d'algorithmes: ceux utilisant la notion de phase logique et les autres qui ne considèrent aucun mécanisme de synchronisation. Ces derniers ont des comportements imprévisibles améliorent la tolérance aux fautes. Nous présentons un nouvel algorithme de ce type associé à une élection qui n'est pas une recherche d'extremum contrairement a l'usage. Cet algorithme est comparable au meilleur algorithme connu qui utilise des jetons et des phases logiques induisant un comportement plus séquentiel. D'autres algorithmes, construisant des ac contraints, sont considèrés. En particulier, l'ac de diamètre minimum qui est, à notre connaissance, un problème qui n'a jamais été étudié dans ce domaine. Le diamètre d'un graphe est la somme des poids des arêtes du plus long des plus courts chemins. Si nous considérons la complexité temporelle, cette contrainte est d'un intérêt évident. Nous proposons différents algorithmes suivant que la tolérance aux fautes est nécessaire ou non. Finalement, l'étude pratique des algorithmes distribués sur des réseaux de grande taille nous a conduit à la construction d'un simulateur. Il permet l'exécution d'un même code source sur des machines séquentielles ou parallèles

Dans cette thèse, nous étudions la complexité algorithmique de problèmes d'optimisation impliquant un processus de diffusion dans un graphe. Plus précisément, nous nous intéressons tout d'abord au problème de sélection d'un ensemble cible. Ce problème consiste à trouver le plus petit ensemble de sommets d'un graphe à "activer" au départ tel que tous les autres sommets soient activés après un nombre fini d'étapes de propagation. Si nous modifions ce processus en permettant de "protéger" un sommet à chaque étape, nous obtenons le problème du pompier dont le but est de minimiser le nombre total de sommets activés en protégeant certains sommets. Dans ce travail, nous introduisons et étudions une version généralisée de ce problème dans laquelle plus d'un sommet peut être protégé à chaque étape. Nous proposons plusieurs résultats de complexité pour ces problèmes à la fois du point de vue de l'approximation mais également de la complexité paramétrée selon des paramètres standards ainsi que des paramètres liés à la structure du graphe.

La colorisation est le processus qui consiste à ajouter des couleurs aux images en niveaux de gris. C’est une tâche importante dans la communauté de l’édition d’images et de l’animation. Bien que des méthodes de colorisation automatique existent, elles produisent souvent des résultats insatisfaisants en raison de défauts tels que le débordement de couleur, l’incohérence, des couleurs non naturelles et la nature non trivial du problème. Par conséquent, une intervention manuelle est souvent nécessaire pour obtenir le résultat souhaité. En conséquence, il y a un intérêt croissant à automatiser le processus de colorisation tout en permettant aux artistes d’ajouter leur propre style et vision. Dans cette thèse, nous étudions divers formats d’interaction en guidant les couleurs sur des zones spécifiques d’une image, ou en les transférant à partir d’une image ou d’un objet de référence. Nous introduisons deux méthodes de colorisation semi-automatiques. Tout d’abord, nous décrivons une architecture d’apprentissage profond pour la colorisation d’images qui prend en compte les images de référence de l’utilisateur. Notre deuxième méthode utilise un modèle de diffusion pour coloriser des dessins en utilisant des indications de couleur fournies par l’utilisateur. Cette thèse commence par l’état de l’art des méthodes de colorisation d’images, des espaces de couleur, des métriques d’évaluation et des fonctions de perte. Bien que les méthodes de colorisation récentes basées sur des techniques d’apprentissage profond obtiennent les meilleurs résultats, ces méthodes sont basées sur des architectures complexes et un grand nombre de fonctions de perte, ce qui rend difficile leur compréhension. Pour cela, nous utilisons une architecture simple afin d’analyser l’impact de différents espaces de couleur et fonctions de perte. Ensuite, nous proposons une nouvelle couche d’attention appelée super-attention qui utilise des superpixels. Elle permet d’établir des correspondances entre les caractéristiques hautes résolutions de paires d’images cible et référence. Cette proposition permet d’atténuer le problème de la complexité quadratique des couches d’attention. De plus, elle aide à surmonter les défauts de débordement de couleur dans la tâche de colorisation. Nous étudions son utilisation pour le transfert de couleur, et pour la colorisation basée sur des exemples. Nous proposons également une extension de ce modèle afin de guider spécifiquement la colorisation sur des objets segmentés. Enfin, nous proposons un modèle de diffusion probabiliste basé sur des conditionnements implicites et explicites, pour apprendre à coloriser des dessins au trait. Notre approche permet d’ajouter des interactions utilisateur à travers des indices de couleur explicites tout en s’appuyant sur l’entraînement du modèle de diffusion principal. Nous utilisons un encodeur spécifique qui apprend à extraire des informations sur les indices de couleur fournis par l’utilisateur. Ce modèle permet d’obtenir des images colorisées diverses et de haute qualité
Colorization is the process of adding colors to grayscale images. It is an important task in the image-editing and animation community. Although automatic colorization methods exist, they often produce unsatisfying results due to artifacts such as color bleeding, inconsistency, unnatural colors, and the ill-posed nature of the problem. Manual intervention is often necessary to achieve the desired outcome. Consequently, there is a growing interest in automating the colorization process while allowing artists to transfer their own style and vision to the process. In this thesis, we investigate various interaction formats by guiding colors of specific areas of an image or transferring them from a reference image or object. As part of this research, we introduce two semi-automatic colorization frameworks. First, we describe a deep learning architecture for exemplar-based image colorization that takes into account user’s reference images. Our second framework uses a diffusion model to colorize line art using user-provided color scribbles. This thesis first delves into a comprehensive overview of state-of-the-art image colorization methods, color spaces, evaluation metrics, and losses. While recent colorization methods based on deep-learning techniques are achieving the best results on this task, these methods are based on complex architectures and a high number of joint losses, which makes the reasoning behind each of these methods difficult. Here, we leverage a simple architecture in order to analyze the impact of different color spaces and several losses. Then, we propose a novel attention layer based on superpixel features to establish robust correspondences between high-resolution deep features from target and reference image pairs, called super-attention. This proposal deals with the quadratic complexity problem of the non-local calculation in the attention layer. Additionally, it helps to overcome color bleeding artifacts. We study its use in color transfer and exemplar-based colorization. We finally extend this model to specifically guide the colorization on segmented objects. Finally, we propose a diffusion probabilistic model based on implicit and explicit conditioning mechanism, to learn colorizing line art. Our approach enables the incorporation of user guidance through explicit color hints while leveraging on the prior knowledge from the trained diffusion model. We condition with an application-specific encoder that learns to extract meaningful information on user-provided scribbles. The method generates diverse and high-quality colorized images

Dans de nombreuses applications telles que la médecine, l'environnement ou les biotechnologies par exemple, la découverte de nouveau processus de régulations de gènes permet une meilleure compréhension des réponses phénotypiques des cellules à des stimuli externes. Pour cela, il est alors d'usage de générer et d'analyser les données transcriptomiques issues d'expériences de types puces à ADN ou plus récemment de RNAseq. Ainsi, pour chaque gène d'un organisme d'étude placé dans différentes conditions expérimentales, un ensemble de niveau d'expression est obtenu. A partir de ces données, les mécanismes de régulation des gènes peuvent être obtenus à travers un ensemble de liens dans des graphes. Dans ces réseaux, les nœuds correspondent aux gènes. A lien entre deux nœuds est identifié si une relation de régulation existent entre les deux gènes correspondant. De tels réseaux sont appelés Réseaux de Régulation de Gènes (RRGs). Malgré la profusion de méthodes d'inférence disponible, leur construction et leur analyse restent encore à ce jour un défi.Dans cette thèse, nous proposons de répondre au problème d'inférence de réseaux par des techniques d'optimisation dans des graphes. A partir d'information de régulation sur l'ensemble des couples de gènes, nous proposons de déterminer la présence d'arêtes dans le RRG final en adoptant une formulation de fonction objectif intégrant des contraintes. Des a priori à la fois biologiques (sur les interactions entre les gènes) et structuraux (sur la connectivité des nœuds) ont été considérés pour restreindre l'espace des solutions possibles. Les différents a priori donnent des fonctions objectifs ayant des propriétés différentes, pour lesquelles des stratégies d'optimisation adaptées (continue et/ou discrète) peuvent être appliquées. Les post-traitement que nous avons développé ont mené à un ensemble de méthodes nommés BRANE, pour "Biologically-Related A priori for Network Enhancement". Pour chacune des méthodes développées (BRANE Cut, BRANE Relax et BRANE Clust), nos contributions sont triples : formulation de la fonction objectif à l'aide d'a priori, développement de la stratégie d'optimisation et validation (numérique et biologique) sur des données de parangonnage issues des challenges DREAM4 et DREAM5, montrant ainsi des améliorations pouvant atteindre 20%.En complément de l'inférence de réseaux, notre travail s'est étendu à des traitements de données sur graphe plus génériques, tels que les problèmes inverses. Nous avons notamment étudié HOGMep, une approche Bayésienne utilisant des stratégies d'approximation Bayésienne variationnelle. Cette méthode a été développée pour résoudre de façon conjointe, des problèmes de restauration et de classification sur des données multi-composantes (signaux et images). Les performances d'HOGMep dans un contexte de déconvolution d'image couleur montrent de bonnes qualités de reconstruction et de segmentation. Une étude préliminaire dans un contexte de classification de données médicales liant génotype et phénotype a également montré des résultats prometteurs pour des adaptions à venir en bioinformatiques
The discovery of novel gene regulatory processes improves the understanding of cell phenotypicresponses to external stimuli for many biological applications, such as medicine, environmentor biotechnologies. To this purpose, transcriptomic data are generated and analyzed from mi-croarrays or more recently RNAseq experiments. For each gene of a studied organism placed indifferent living conditions, they consist in a sequence of genetic expression levels. From thesedata, gene regulation mechanisms can be recovered by revealing topological links encoded ingeometric graphs. In regulatory graphs, nodes correspond to genes. A link between two nodesis identified if a regulation relationship exists between the two corresponding genes. Such net-works are called Gene Regulatory Networks (GRNs). Their construction as well as their analysisremain challenging despite the large number of available inference methods.In this thesis, we propose to address this network inference problem with recently developedtechniques pertaining to graph optimization. Given all the pairwise gene regulation informa-tion available, we propose to determine the presence of edges in the final GRN by adoptingan energy optimization formulation integrating additional constraints. Either biological (infor-mation about gene interactions) or structural (information about node connectivity) a priorihave been considered to reduce the space of possible solutions. Different priors lead to differentproperties of the global cost function, for which various optimization strategies can be applied.The post-processing network refinements we proposed led to a software suite named BRANE for“Biologically-Related A priori for Network Enhancement”. For each of the proposed methodsBRANE Cut, BRANE Relax and BRANE Clust, our contributions are threefold: a priori-based for-mulation, design of the optimization strategy and validation (numerical and/or biological) onbenchmark datasets.In a ramification of this thesis, we slide from graph inference to more generic data processingsuch as inverse problems. We notably invest in HOGMep, a Bayesian-based approach using aVariation Bayesian Approximation framework for its resolution. This approach allows to jointlyperform reconstruction and clustering/segmentation tasks on multi-component data (for instancesignals or images). Its performance in a color image deconvolution context demonstrates bothquality of reconstruction and segmentation. A preliminary study in a medical data classificationcontext linking genotype and phenotype yields promising results for forthcoming bioinformaticsadaptations

L'objectif de cette thèse est le développement d'algorithmes et de modèles permettant l'optimisation d'itinéraires dans les réseaux routiers. Dans un premier temps, ce travail de recherche étudie le problème de l'interception d'un mobile dans un graphe. Dans ce contexte, l'objectif est de calculer un itinéraire optimal permettant de rejoindre une cible mobile dont la trajectoire est connue. Cette problématique est traitée pour plusieurs situations (un poursuivant/un objectif et plusieurs poursuivants/plusieurs objectifs) et pour plusieurs types de graphes (graphes statiques et graphes FIFO). Pour chaque cas, un algorithme de résolution est proposé et l'optimalité du résultat qu'il retourne est démontrée. De plus, un ensemble de simulations est réalisé afin de vérifier l'efficacité des algorithmes en termes de temps de calcul. Dans un deuxième temps, une nouvelle classe de graphes dynamiques est définie : les graphes dynamiques avec intervalles. La particularité de ces graphes est que le poids de chaque arc dépende du temps et qu'il est représenté par un intervalle. Pour ce nouveau type de graphes, le problème du plus court chemin est étudié. Ce problème peut être vu soit en tant que problème d'optimisation monocritère soit en tant que problème d'optimisation multicritère. Pour chaque cas, le problème est formulé et des approches pour la résolution sont proposées.

Cette thèse est motivée par l’analyse des données issues de l’imagerie par résonance magnétique fonctionnelle (IRMf). La nécessité de développer des méthodes capables d’extraire la structure sous-jacente des données d’IRMf constitue un challenge mathématique attractif. A cet égard, nous modélisons les réseaux de connectivité cérébrale par un graphe et nous étudions des procédures permettant d’inférer ce graphe.Plus précisément, nous nous intéressons à l’inférence de la structure d’un modèle graphique non orienté par une procédure de test multiple. Nous considérons deux types de structure, à savoir celle induite par la corrélation et celle induite par la corrélation partielle entre les variables aléatoires. Les statistiques de tests basées sur ces deux dernières mesures sont connues pour présenter une forte dépendance et nous les supposerons être asymptotiquement gaussiennes. Dans ce contexte, nous analysons plusieurs procédures de test multiple permettant un contrôle des arêtes incluses à tort dans le graphe inféré.Dans un premier temps, nous questionnons théoriquement le contrôle du False Discovery Rate (FDR) de la procédure de Benjamini et Hochberg dans un cadre gaussien pour des statistiques de test non nécessairement positivement dépendantes. Nous interrogeons par suite le contrôle du FDR et du Family Wise Error Rate (FWER) dans un cadre gaussien asymptotique. Nous présentons plusieurs procédures de test multiple, adaptées aux tests de corrélations (resp. corrélations partielles), qui contrôlent asymptotiquement le FWER. Nous proposons de plus quelques pistes théoriques relatives au contrôle asymptotique du FDR.Dans un second temps, nous illustrons les propriétés des procédures contrôlant asymptotiquement le FWER à travers une étude sur simulation pour des tests basés sur la corrélation. Nous concluons finalement par l’extraction de réseaux de connectivité cérébrale sur données réelles
This thesis is motivated by the analysis of the functional magnetic resonance imaging (fMRI). The need for methods to build such structures from fMRI data gives rise to exciting new challenges for mathematics. In this regards, the brain connectivity networks are modelized by a graph and we study some procedures that allow us to infer this graph.More precisely, we investigate the problem of the inference of the structure of an undirected graphical model by a multiple testing procedure. The structure induced by both the correlation and the partial correlation are considered. The statistical tests based on the latter are known to be highly dependent and we assume that they have an asymptotic Gaussian distribution. Within this framework, we study some multiple testing procedures that allow a control of false edges included in the inferred graph.First, we theoretically examine the False Discovery Rate (FDR) control of Benjamini and Hochberg’s procedure in Gaussian setting for non necessary positive dependent statistical tests. Then, we explore both the FDR and the Family Wise Error Rate (FWER) control in asymptotic Gaussian setting. We present some multiple testing procedures, well-suited for correlation (resp. partial correlation) tests, which provide an asymptotic control of the FWER. Furthermore, some first theoretical results regarding asymptotic FDR control are established.Second, the properties of the multiple testing procedures that asymptotically control the FWER are illustrated on a simulation study, for statistical tests based on correlation. We finally conclude with the extraction of cerebral connectivity networks on real data set

L’objectif de cette thèse est d’attribuer à chaque sommet x d’un graphe G à n sommets une étiquette L(x) de taille compacte O(log n) bits afin de pouvoir :1. construire, à partir des étiquettes d’un ensemble de sommets en panne X C V (G), une structure de donnée S(X)2. décider, à partir de S(X) et des étiquettes L(u) et L(v), si les sommets u et v sont connectés dans le graphe G n X.Nous proposons une solution à ce problème pour la famille des graphes 3-connexes de genre g (via plusieurs résultats intermédiaires).— Les étiquettes sont de taille O(g log n) bits— Le temps de construction de la structure de donnée S(X) est O(Sort([X]; n)).— Le temps de décision est O(log log n). Ce temps est optimal.Nous étendons ce résultat à la famille des graphes excluant un mineur H fixé. Les étiquettes sont ici de taille O(polylog n) bits
We aim at assigning each vertex x of a n-vertices graph G a compact O(log n)-bit label L(x) in order to :1. construct, from the labels of the vertices of a forbidden set X C V (G), a datastructure S(X)2. decide, from S(X), L(u) and L(v), whether two vertices u and v are connected in G n X.We give a solution to this problem for the family of 3-connected graphs whith bounded genus.— We obtain O(g log n)-bit labels.— S(X) is computed in O(Sort([X]; n)) time.— Connection between vertices is decided in O(log log n) optimal time.We finally extend this result to H-minor-free graphs. This scheme requires O(polylog n)-bit labels

Cette thèse définit un nouveau modèle de calcul et de communication, dénommé graphe à routage k-périodique (KRG). Ce modèle, de la famille des réseaux de processus flots de données, admet des aiguillages réguliers des données, explicités par des séquences binaires k-périodiques. Nous étudions les propriétés mathématiques intrinsèques au modèle. Le routage explicite et l'absence de conflit nous permettent d'exprimer algébriquement les dépendances de données, de même que des transformations topologiques préservant le comportement du graphe. Nous montrons ensuite comment ordonnancer le KRG, en associant aux nœuds des horloges k-périodiques. Nous positionnons ensuite notre modèle au sein d'un flot de conception dédié aux applications de traitement intensif de données. Nous montrons en particulier la capacité des KRG à représenter explicitement le parallélisme d'instruction extrait du modèle polyédrique. Nous pouvons alors appliquer un ensemble d'optimisations de bas niveau, sortant du cadre affine du modèle polyédrique. Nous présentons enfin une méthodologie pour l'implantation des KRG, basée sur la conception insensible aux latences.

Au sein de la communauté scientifique, l’étude des réseaux d’énergie suscite un vif intérêt puisque ces infrastructures deviennent de plus en plus importantes dans notre monde moderne. Des outils mathématiques avancés et complexes sont nécessaires afin de bien concevoir et mettre en œuvre ces réseaux. La précision et l’optimalité sont deux caractéristiques essentielles pour leur conception. Bien que ces deux aspects soient au cœur des méthodes formelles, leur application effective reste largement inexplorée aux réseaux d’énergie. Cela motive fortement le travail développé dans cette thèse. Un accent particulier est placé sur le problème général de planification de la consommation d'énergie. Il s'agit d'un scénario dans lequel les consommateurs ont besoin d’une certaine quantité d’énergie et souhaitent que cette demande soit satisfaite dans une période spécifique (e.g., un Véhicule Électrique (VE) doit être rechargé dans une fenêtre de temps définie par son propriétaire). Par conséquent, chaque consommateur doit choisir une puissance de consommation à chaque instant (par un système informatisé), afin que l'énergie finale accumulée atteigne un niveau souhaité. La manière dont les puissances sont choisies est obtenue par l’application d’une « stratégie » qui prend en compte à chaque instant les informations pertinentes d'un consommateur afin de choisir un niveau de consommation approprié (e.g., l’énergie accumulée pour recharge le VE). Les stratégies peuvent être conçues selon une approche centralisée (dans laquelle il n'y a qu'un seul décideur qui contrôle toutes les stratégies des consommateurs) ou décentralisée (dans laquelle il y a plusieurs contrôleurs, chacun représentant un consommateur). Nous analysons ces deux scénarios dans cette thèse en utilisant des méthodes formelles, la théorie des jeux et l’optimisation. Plus précisément, nous modélisons le problème de planification de la consommation d'énergie à l'aide des processus de décision de Markov et des jeux stochastiques. Par exemple, l’environnement du système électrique, à savoir : la partie non contrôlable de la consommation totale (e.g., la consommation hors VEs), peut être représentée par un modèle stochastique. La partie contrôlable de la consommation totale peut s’adapter aux contraintes du réseau de distribution (e.g., pour ne pas dépasser la température maximale d'arrêt du transformateur électrique) et à leurs objectifs (e.g., tous les VEs soient rechargés). Cela peut être vu comme un système stochastique avec des multi-objectifs sous contraintes. Par conséquent, cette thèse concerne également une contribution aux modèles avec des objectives multicritères, ce qui permet de poursuivre plusieurs objectifs à la fois et une conception des stratégies qui sont fonctionnellement correctes et robustes aux changements de l'environnement
Within the research community, there is a great interest in exploring many applications of energy grids since these become more and more important in our modern world. To properly design and implement these networks, advanced and complex mathematical tools are necessary. Two key features for their design are correctness and optimality. While these last two properties are in the core of formal methods, their effective application to energy networks remains largely unexploited. This constitutes one strong motivation for the work developed in this thesis. A special emphasis is made on the generic problem of scheduling power consumption. This is a scenario in which the consumers have a certain energy demand and want to have this demand fulfilled before a set deadline (e.g., an Electric Vehicle (EV) has to be recharged within a given time window set by the EV owner). Therefore, each consumer has to choose at each time the consumption power (by a computerized system) so that the final accumulated energy reaches a desired level. The way in which the power levels are chosen is according to a ``strategy’’ mapping at any time the relevant information of a consumer (e.g., the current accumulated energy for EV-charging) to a suitable power consumption level. The design of such strategies may be either centralized (in which there is a single decision-maker controlling all strategies of consumers), or decentralized (in which there are several decision-makers, each of them representing a consumer). We analyze both scenarios by exploiting ideas originating from formal methods, game theory and optimization. More specifically, the power consumption scheduling problem can be modelled using Markov decision processes and stochastic games. For instance, probabilities provide a way to model the environment of the electrical system, namely: the noncontrollable part of the total consumption (e.g., the non-EV consumption). The controllable consumption can be adapted to the constraints of the distribution network (e.g., to the maximum shutdown temperature of the electrical transformer), and to their objectives (e.g., all EVs are recharged). At first glance, this can be seen as a stochastic system with multi-constraints objectives. Therefore, the contributions of this thesis also concern the area of multi-criteria objective models, which allows one to pursue several objectives at a time such as having strategy designs functionally correct and robust against changes of the environment

Nous présentons dans cette thèse une étude sur des
algorithmes distribués asynchrones et déterministes de
contröle. Un système distribué consiste en un réseau
de sites (processeurs, ordinateurs ou réseaux locaux). Dans cette
thèse, nous ne considérons que des réseaux de sites
communicants n'ayant ni mémoire partagée ni horloge globale.
De nombreux problèmes de l'algorithmique distribuée sont
réductibles à la construction d'un Arbre Couvrant qui est la
structure de contrôle qui nous intéresse.

Nous étudions deux types d'algorithmes~: ceux utilisant
la notion de phase logique et les autres qui ne considèrent aucun
mécanisme de synchronisation. Ces derniers ont des comportements
imprévisibles améliorant la tolérance aux fautes. Nous
présentons un nouvel algorithme de ce type associé à une
élection qui n'est pas une recherche d'extremum contrairement
à l'usage. Cet algorithme est comparable au meilleur
algorithme connu qui utilise des jetons et des phases logiques
induisant un comportement plus "séquentiel".

D'autres algorithmes, construisant des AC contraints, sont
considérés. En particulier l'AC de Diamètre Minimum qui
est, à notre connaissance, un problème qui n'a jamais
été étudié dans ce domaine. Le diamètre d'un
graphe est la somme des poids des arêtes du plus long des plus
courts chemins. Si nous considérons la complexité temporelle,
cette contrainte est d'un intérêt &vident. Nous proposons
différents algorithmes suivant que la tolérance aux fautes est
nécessaire ou non.

Finalement, l'étude pratique des algorithmes distribués sur
des réseaux de grande taille nous a conduit à la construction
d'un simulateur. Il permet l'exécution d'un même code source
sur des machines séquentielles ou parallèles.

Cette thèse s'intéresse aux réseaux de confusion comme représentation compacte et structurée des hypothèses multiples produites par un moteur de reconnaissance de parole et transmises à un module de post-traitement applicatif. Les réseaux de confusion (CN pour Confusion Networks) sont générés à partir des graphes de mots et structurent l'information sous la forme d'une séquence de classes contenant des hypothèses de mots en concurrence. Le cas d'usage étudié dans ces travaux est celui des hypothèses de reconnaissance transmises à un module de compréhension de la parole dans le cadre d'une application de dialogue déployée par France Telecom. Deux problématiques inhérentes à ce contexte applicatif sont soulevées. De façon générale, un système de dialogue doit non seulement reconnaître un énoncé prononcé par un utilisateur, mais aussi l'interpréter afin de déduire sons sens. Du point de vue de l'utilisateur, les performances perçues sont plus proches de celles de la chaîne complète de compréhension que de celles de la reconnaissance vocale seule. Ce sont ces performances que nous cherchons à optimiser. Le cas plus particulier d'une application déployée implique de pouvoir traiter des données réelles et donc très variées. Un énoncé peut être plus ou moins bruité, dans le domaine ou hors-domaine, couvert par le modèle sémantique de l'application ou non, etc. Étant donnée cette grande variabilité, nous posons la question de savoir si le fait d'appliquer les mêmes traitements sur l'ensemble des données, comme c'est le cas dans les approches classiques, est une solution adaptée. Avec cette double perspective, cette thèse s'attache à la fois à enrichir l'algorithme de construction des CNs dans le but d'optimiser globalement le processus de compréhension et à proposer une stratégie adéquate d'utilisation des réseaux de confusion dans le contexte d'une application réelle. Après une analyse des propriétés de deux approches de construction des CNs sur un corpus de données réelles, l'algorithme retenu est celui du "pivot". Nous en proposons une version modifiée et adaptée au contexte applicatif en introduisant notamment un traitement différencié des mots du graphe qui privilégie les mots porteurs de sens. En réponse à la grande variabilité des énoncés à traiter dans une application déployée, nous proposons une stratégie de décision à plusieurs niveaux qui vise à mieux prendre en compte les spécificités des différents types d'énoncés. Nous montrons notamment qu'il est préférable de n'exploiter la richesse des sorties multiples que sur les énoncés réellement porteurs de sens. Cette stratégie permet à la fois d'optimiser les temps de calcul et d'améliorer globalement les performances du système

Cette thèse présente de nouvelles méthodes d’apprentissage structuré et parcimonieux sur les graphes, ce qui permet de résoudre une large variété de problèmes d’imagerie cérébrale, ainsi que d’autres problèmes en haute dimension avec peu d’échantillon. La première partie de cette thèse propose des relaxation convexe de pénalité discrète et combinatoriale impliquant de la parcimonie et bounded total variation d’un graphe, ainsi que la bounded `2. Ceux-ci sont dévelopé dansle but d’apprendre un modèle linéaire interprétable et on démontre son efficacacité sur des données d’imageries cérébrales ainsi que sur les problèmes de reconstructions parcimonieux.Les sections successives de cette thèse traite de la découverte de structure sur des modèles graphiques “undirected” construit à partir de peu de données. En particulier, on se concentre sur des hypothèses de parcimonie et autres hypothèses de structures dans les modèles graphiques gaussiens. Deux contributions s’en dégagent. On construit une approche pour identifier les différentes entre des modèles graphiques gaussiens (GGMs) qui partagent la même structure sous-jacente. On dérive la distribution de différences de paramètres sous une pénalité jointe quand la différence des paramètres est parcimonieuse. On montre ensuite comment cette approche peut être utilisée pour obtenir des intervalles de confiances sur les différences prises par le GGM sur les arêtes. De là, on introduit un nouvel algorithme d’apprentissage lié au problème de découverte de structure sur les modèles graphiques non dirigées des échantillons observés. On démontre que les réseaux de neurones peuvent être utilisés pour apprendre des estimateurs efficacaces de ce problèmes. On montre empiriquement que ces méthodes sont une alternatives flexible et performantes par rapport aux techniques existantes
This dissertation presents novel structured sparse learning methods on graphs that address commonly found problems in the analysis of neuroimaging data as well as other high dimensional data with few samples. The first part of the thesis proposes convex relaxations of discrete and combinatorial penalties involving sparsity and bounded total variation on a graph as well as bounded `2 norm. These are developed with the aim of learning an interpretable predictive linear model and we demonstrate their effectiveness on neuroimaging data as well as a sparse image recovery problem.The subsequent parts of the thesis considers structure discovery of undirected graphical models from few observational data. In particular we focus on invoking sparsity and other structured assumptions in Gaussian Graphical Models (GGMs). To this end we make two contributions. We show an approach to identify differences in Gaussian Graphical Models (GGMs) known to have similar structure. We derive the distribution of parameter differences under a joint penalty when parameters are known to be sparse in the difference. We then show how this approach can be used to obtain confidence intervals on edge differences in GGMs. We then introduce a novel learning based approach to the problem structure discovery of undirected graphical models from observational data. We demonstrate how neural networks can be used to learn effective estimators for this problem. This is empirically shown to be flexible and efficient alternatives to existing techniques

Pour faire face aux mutations du paysage énergétique, les réseaux de distribution d'électricité sont soumis à des exigences de fonctionnement avec des indices de fiabilité à garantir. Dans les années à venir, de grands investissements sont prévus pour la construction des réseaux électriques flexibles, cohérents et efficaces, basés sur de nouvelles architectures et des solutions techniques innovantes, adaptatifs à l'essor des énergies renouvelables. En prenant en compte ces besoins industriels sur le développement des réseaux de distribution du futur, nous proposons, dans cette thèse, une approche reposant sur la théorie des graphes et l'optimisation combinatoire pour la conception de nouvelles architectures pour les réseaux de distribution. Notre démarche consiste à étudier le problème général de recherche d'une architecture optimale qui respecte l'ensemble de contraintes topologiques (redondance) et électrotechniques (courant maximal, plan de tension) selon des critères d'optimisation bien précis : minimisation du coût d'exploitation (OPEX) et minimisation de l'investissement (CAPEX). Ainsi donc, les deux familles des problèmes combinatoires (et leurs relaxations) ont été explorées pour proposer des résolutions efficaces (exactes ou approchées) du problème de planification des réseaux de distribution en utilisant une formulation adaptée. Nous nous sommes intéressés particulièrement aux graphes 2-connexes et au problème de flot arborescent avec pertes quadratiques minimales. Les résultats comparatifs de tests sur les instances de réseaux (fictifs et réels) pour les méthodes proposées ont été présentés
To cope with the changes in the energy landscape, electrical distribution networks are submitted to operational requirements in order to guarantee reliability indices. In the coming years, big investments are planned for the construction of flexible, consistent and effective electrical networks, based on the new architectures, innovative technical solutions and in response to the development of renewable energy. Taking into account the industrial needs of the development of future distribution networks, we propose in this thesis an approach based on the graph theory and combinatorial optimization for the design of new architectures for distribution networks. Our approach is to study the general problem of finding an optimal architecture which respects a set of topological (redundancy) and electrical (maximum current, voltage plan) constraints according to precise optimization criteria: minimization of operating cost (OPEX) and minimization of investment (CAPEX). Thus, the two families of combinatorial problems (and their relaxations) were explored to propose effective resolutions (exact or approximate) of the distribution network planning problem using an adapted formulation. We are particularly interested in 2-connected graphs and the arborescent flow problem with minimum quadratic losses. The comparative results of tests on the network instances (fictional and real) for the proposed methods were presented

Le développement d'algorithmes efficaces pour apprendre des représentations appropriées des données structurées, telles des sequences ou des graphes, est un défi majeur et central de l'apprentissage automatique. Pour atteindre cet objectif, l'apprentissage profond est devenu populaire pour modéliser des données structurées. Les réseaux de neurones profonds ont attiré une attention particulière dans divers domaines scientifiques tels que la vision par ordinateur, la compréhension du langage naturel ou la biologie. Par exemple, ils fournissent aux biologistes des outils de calcul qui leur permettent de comprendre et de découvrir les propriétés biologiques ou les relations entre les macromolécules des organismes vivants. Toutefois, leur succès dans ces domaines repose essentiellement sur des connaissances empiriques ainsi que d'énormes quantités de données annotées. Exploiter des modèles plus efficaces est nécessaire car les données annotées sont souvent rares.Un autre axe de recherche est celui des méthodes à noyaux, qui fournissent une approche systématique et fondée sur des principes théoriquement solides pour l'apprentissage de modèles non linéaires à partir de données de structure arbitraire. Outre leur simplicité, elles présentent une manière naturelle de contrôler la régularisation et ainsi d'éviter le surapprentissage.Cependant, les représentations de données fournies par les méthodes à noyaux ne sont définies que par des caractéristiques artisanales simplement conçues, ce qui les rend moins performantes que les réseaux de neurones lorsque suffisamment de données étiquetées sont disponibles. Des noyaux plus complexes, inspirés des connaissances préalables utilisées dans les réseaux de neurones, ont ainsi été développés pour construire des représentations plus riches et ainsi combler cette lacune. Pourtant, ils sont moins adaptatifs. Par comparaison, les réseaux de neurones sont capables d'apprendre une représentation compacte pour une tâche d'apprentissage spécifique, ce qui leur permet de conserver l'expressivité de la représentation tout en s'adaptant à une grande taille d'échantillon.Il est donc utile d'intégrer les vues complémentaires des méthodes à noyaux et des réseaux de neurones profonds pour construire de nouveaux cadres afin de bénéficier du meilleur des deux mondes.Dans cette thèse, nous construisons un cadre général basé sur les noyaux pour la modélisation des données structurées en tirant parti des connaissances préalables des méthodes à noyaux classiques et des réseaux profonds. Notre cadre fournit des outils algorithmiques efficaces pour l'apprentissage de représentations sans annotations ainsi que pour l'apprentissage de représentations plus compactes de manière supervisée par les tâches. Notre cadre peut être utilisé pour modéliser efficacement des séquences et des graphes avec une interprétation simple. Il offre également de nouvelles perspectives sur la construction des noyaux et de réseaux de neurones plus expressifs pour les séquences et les graphes
Developing efficient algorithms to learn appropriate representations of structured data, including sequences or graphs, is a major and central challenge in machine learning. To this end, deep learning has become popular in structured data modeling. Deep neural networks have drawn particular attention in various scientific fields such as computer vision, natural language understanding or biology. For instance, they provide computational tools for biologists to possibly understand and uncover biological properties or relationships among macromolecules within living organisms. However, most of the success of deep learning methods in these fields essentially relies on the guidance of empirical insights as well as huge amounts of annotated data. Exploiting more data-efficient models is necessary as labeled data is often scarce.Another line of research is kernel methods, which provide a systematic and principled approach for learning non-linear models from data of arbitrary structure. In addition to their simplicity, they exhibit a natural way to control regularization and thus to avoid overfitting.However, the data representations provided by traditional kernel methods are only defined by simply designed hand-crafted features, which makes them perform worse than neural networks when enough labeled data are available. More complex kernels inspired by prior knowledge used in neural networks have thus been developed to build richer representations and thus bridge this gap. Yet, they are less scalable. By contrast, neural networks are able to learn a compact representation for a specific learning task, which allows them to retain the expressivity of the representation while scaling to large sample size.Incorporating complementary views of kernel methods and deep neural networks to build new frameworks is therefore useful to benefit from both worlds.In this thesis, we build a general kernel-based framework for modeling structured data by leveraging prior knowledge from classical kernel methods and deep networks. Our framework provides efficient algorithmic tools for learning representations without annotations as well as for learning more compact representations in a task-driven way. Our framework can be used to efficiently model sequences and graphs with simple interpretation of predictions. It also offers new insights about designing more expressive kernels and neural networks for sequences and graphs

Les neurones impulsionnels prennent en compte une caractéristique fondamentale des neurones biologiques : la capacité d'encoder l'information sous forme d'événements discrets. Nous nous sommes intéressés à l'apport de ce type de modèles dans le cadre de la vision artificielle, dont les contraintes nous ont orienté vers le choix de modèles simples, adaptés à la rapidité de traitement requise. Nous décrivons une architecture de réseaux pour encoder et extraire des saillances utilisant la discrétisation induite par les neurones impulsionnels. La carte de saillances est obtenue à partir de la combinaison, spatiale et temporelle, de différentes cartes de modalités visuelles (contrastes, orientations et couleurs) à différentes échelles spatiales. Nous proposons une méthode de filtrage neuronal pour construire les cartes de modalité visuelle. Cette méthode réalise le filtrage de façon graduelle : plus le temps de traitement alloué à l'algorithme est important, plus le résultat est proche de celui obtenu avec un filtrage par convolution. L'architecture proposée donne en sortie les saillances triées temporellement dans l'ordre de leur importance. Nous avons placé en aval de cette architecture un autre réseau de neurones impulsionnels, s'inspirant des champs neuronaux, qui permet de sélectionner la zone la plus saillante et de maintenir une activité constante sur cette zone. Les résultats expérimentaux montrent que l'architecture proposée est capable d'extraire des saillances dans une séquence d'images, de sélectionner la saillance la plus importante et de maintenir la focalisation sur cette saillance, même dans un contexte bruité ou quand la saillance se déplace.

Les travaux présentés dans cette thèse constituent une contribution à la modélisation, à l'analyse et à la commande des systèmes de transport public par l'adaptation des réseaux de Petri (RdP) et algèbre des dioïdes. Nous étudions en particulier la gestion optimisée des correspondances par une planification des horaires d'un réseau de transport en commun. Nous développons dans ce sens des modèles capables d'apporter des solutions aux problèmes d'amélioration de la qualité de service de transport en commun, par les minimisations des temps de correspondance et des ressources matérielles utilisées. Notre travail est effectué en considérant deux études de cas de fonctionnement des bus au niveau des arrêts de correspondance où des échanges de passagers sont susceptibles de se produire. Un fonctionnement synchronisé pour lequel nous utilisons un modèle graphe d'événements temporisés (GET) et un modèle (max, +) linéaire stationnaire qui lui est associé. Un fonctionnement non-synchronisé modélisé par un graphe d'événements temporisés avec retrait dynamique de jetons (GETRDJ). Ce dernier modèle graphique, possédant des conflits structurels, a une description analytique dans l'algèbre (max, +) de forme linéaire non-stationnaire. La résolution mathématique du modèle obtenu passe par une politique de résolution des conflits associés au modèle graphique. Nous proposons dans ce sens une politique de routage déterminée a priori prenant en compte les caractéristiques du système. Cette politique permet d'une part, d'arbitrer les conflits sur le modèle graphique, et d'autre part, de résoudre le modèle mathématique. L'analyse des solutions obtenues ainsi que les éléments propres de la matrice caractéristique du modèle (max, +) permet de déterminer les différents temps de correspondance des voyageurs et d'estimer ainsi les performances du système étudié. Dans le souci de minimiser les temps de correspondance des voyageurs et améliorer la qualité de service, nous proposons une politique de commande de ces réseaux de bus. Deux approches sont alors proposées. La première permet de synthétiser une commande basée sur les techniques développées dans le cadre de la théorie de la résiduation dans les dioïdes. La seconde est fondée sur des résultats de simulation qui permettent d'obtenir une commande à partir des optima globaux des fonctions objectifs. Les résultats obtenus sont validés sur une partie du réseau de transport en commun de la ville de Montbéliard.

Cette thèse propose des modèles et des méthodes pour étudier le contrôle du risque dans de larges systèmes financiers. Nous proposons dans une première partie une approche structurelle : nous considérons un système financier représenté comme un réseau d’institutions connectées entre elles par des interactions stratégiques sources de financement mais également par des interactions qui les exposent à un risque de contagion de défaut. La nouveauté de notre approche réside dans le fait que ces deux types d’interaction interfèrent. Nous proposons des nouvelles notions d’équilibre pour ces systèmes et étudions la connectivité optimale du réseau et le risque systémique associé. Dans une deuxième partie, nous introduisons des mesures de risque systémique définies par des équations différentielles stochastiques rétrogrades dirigées par des opérateurs à champ moyen et étudions des problèmes d’arrêt optimal associés. La dernière partie aborde des questions de liquidation optimale de portefeuilles
This thesis presents models and methodologies to understand the control of systemic risk in large systems. We propose two approaches. The first one is structural : a financial system is represented as a network of institutions. They have strategic interactions as well as direct interactions through linkages in a contagion process. The novelty of our approach is that these two types of interactions are intertwined themselves and we propose new notions of equilibria for such games and analyze the systemic risk emerging in equilibrium. The second approach is a reduced form.We model the dynamics of regulatory capital using a mean field operator : required capital depends on the standalone risk but also on the evolution of the capital of all other banks in the system. In this model, required capital is a dynamic risk measure and is represented as a the solution of a mean-field BDSE with jumps. We show a novel dual representation theorem. In the context of meanfield BSDEs the representation gives yield to a stochastic discount factor and a worst-case probability measure that encompasses the overall interactions in the system. We also solve the optimal stopping problem of dynamic risk measure by connecting it to the solution of reflected meanfield BSDE with jumps. Finally, We provide a comprehensive model for the order book dynamics and optimal Market making strategy appeared in liquidity risk problems

Cette thèse est réalisée dans le cadre du projet BPI DeepTech, en collaboration avec la société Fair&Smart, veillant principalement à la protection des données personnelles conformément au Règlement Général sur la Protection des Données (RGPD). Dans ce contexte, nous avons proposé un modèle neuronal profond pour l'extraction d'informations dans les documents administratifs semi-structurés (DSSs). En raison du manque de données d'entraînement publiques, nous avons proposé un générateur artificiel de DSSs qui peut générer plusieurs classes de documents avec une large variation de contenu et de mise en page. Les documents sont générés à l'aide de variables aléatoires permettant de gérer le contenu et la mise en page en respectant des contraintes visant à garantir leur proximité avec des documents réels. Des métriques ont été introduites pour évaluer la diversité des DSSs générés en termes de contenu et de mise en page. Les résultats de l'évaluation ont montré que les jeux de données générés pour trois types de DSSs (fiches de paie, tickets de caisse et factures) présentent un degré élevé de diversité, ce qui permet d'éviter le sur-apprentissage lors de l'entraînement des systèmes d'extraction d'informations. En s'appuyant sur le format spécifique des DSSs, constitué de paires de mots (mots-clés, informations) situés dans des voisinages proches spatialement, le document est modélisé sous forme de graphe où les nœuds représentent les mots et les arcs, les relations de voisinage. Le graphe est incorporé dans un réseau d'attention à graphe (GAT) multi-couches (Multi-GAT). Celui-ci applique le mécanisme d'attention multi-têtes permettant d'apprendre l'importance des voisins de chaque mot pour mieux le classer. Une première version de ce modèle a été utilisée en mode supervisé et a obtenu un score F1 de 96 % sur deux jeux de données de factures et de fiches de paie générées, et de 89 % sur un ensemble de tickets de caisse réels (SROIE). Nous avons ensuite enrichi le Multi-GAT avec un plongement multimodal de l'information au niveau des mots (avec des composantes textuelle, visuelle et positionnelle), et l'avons associé à un auto-encodeur variationnel à graphe (VGAE). Ce modèle fonctionne en mode semi-supervisé, capable d'apprendre à partir des données annotées et non annotées simultanément. Pour optimiser au mieux la classification des nœuds du graphe, nous avons proposé un semi-VGAE dont l'encodeur partage ses premières couches avec le classifieur Multi-GAT. Cette optimisation est encore renforcée par la proposition d'une fonction de perte VGAE gérée par la perte de classification. En utilisant une petite base de données non annotées, nous avons pu améliorer de plus de 3 % le score F1 obtenu sur un ensemble de factures générées. Destiné à fonctionner dans un environnement protégé, nous avons adapté l'architecture du modèle pour son chiffrement homomorphe. Nous avons étudié une méthode de réduction de la dimensionnalité du modèle Multi-GAT. Ensuite, nous avons proposé une approche d'approximation polynomiale des fonctions non-linéaires dans le modèle. Pour réduire la dimension du modèle, nous avons proposé une méthode de fusion de caractéristiques multimodales qui nécessite peu de paramètres supplémentaires et qui réduit les dimensions du modèle tout en améliorant ses performances. Pour l'adaptation au chiffrement, nous avons étudié des approximations polynomiales de degrés faibles aux fonctions non-linéaires avec une utilisation des techniques de distillation de connaissance et de fine tuning pour mieux adapter le modèle aux nouvelles approximations. Nous avons pu minimiser la perte lors de l'approximation d'environ 3 % pour deux jeux de données de factures ainsi qu'un jeu de données de fiches de paie et de 5 % pour SROIE
This thesis is being carried out as part of the BPI DeepTech project, in collaboration with the company Fair&Smart, primarily looking after the protection of personal data in accordance with the General Data Protection Regulation (RGPD). In this context, we have proposed a deep neural model for extracting information in semi-structured administrative documents (SSDs). Due to the lack of public training datasets, we have proposed an artificial generator of SSDs that can generate several classes of documents with a wide variation in content and layout. Documents are generated using random variables to manage content and layout, while respecting constraints aimed at ensuring their similarity to real documents. Metrics were introduced to evaluate the content and layout diversity of the generated SSDs. The results of the evaluation have shown that the generated datasets for three SSD types (payslips, receipts and invoices) present a high diversity level, thus avoiding overfitting when training the information extraction systems. Based on the specific format of SSDs, consisting specifically of word pairs (keywords-information) located in spatially close neighborhoods, the document is modeled as a graph where nodes represent words and edges, neighborhood connections. The graph is fed into a multi-layer graph attention network (Multi-GAT). The latter applies the multi-head attention mechanism to learn the importance of each word's neighbors in order to better classify it. A first version of this model was used in supervised mode and obtained an F1 score of 96% on two generated invoice and payslip datasets, and 89% on a real receipt dataset (SROIE). We then enriched the multi-GAT with multimodal embedding of word-level information (textual, visual and positional), and combined it with a variational graph auto-encoder (VGAE). This model operates in semi-supervised mode, being able to learn on both labeled and unlabeled data simultaneously. To further optimize the graph node classification, we have proposed a semi-VGAE whose encoder shares its first layers with the multi-GAT classifier. This is also reinforced by the proposal of a VGAE loss function managed by the classification loss. Using a small unlabeled dataset, we were able to improve the F1 score obtained on a generated invoice dataset by over 3%. Intended to operate in a protected environment, we have adapted the architecture of the model to suit its homomorphic encryption. We studied a method of dimensionality reduction of the Multi-GAT model. We then proposed a polynomial approximation approach for the non-linear functions in the model. To reduce the dimensionality of the model, we proposed a multimodal feature fusion method that requires few additional parameters and reduces the dimensions of the model while improving its performance. For the encryption adaptation, we studied low-degree polynomial approximations of nonlinear functions, using knowledge distillation and fine-tuning techniques to better adapt the model to the new approximations. We were able to minimize the approximation loss by around 3% on two invoice datasets as well as one payslip dataset and by 5% on SROIE

Cette thèse étudie les capacités des méthodes d'apprentissage automatique à raisonner sur des relations spatiales, en particulier sur les relations directionnelles, et l'utilisation de connaissances relationnelles, connues a priori, par ces méthodes. Il existe de nombreux travaux dans le domaine de l'exploitation de connaissances sur les relations dans des méthodes d'apprentissage automatique. Cependant, ce corpus de travaux laisse encore plusieurs questions ouvertes. Tout au long de cette thèse, nous explorons, étudions et tentons d'expliquer différentes questions de recherche liées à ces questions.Nous proposons une amélioration de l'apprentissage des réseaux de neurones convolutionnels (CNN) via une fonction de coût de régularisation intégrant l'information relationnelle. Pour cela, nous proposons deux nouvelles fonctions de coût qui favorisent la satisfaction des relations pendant l'entraînement des CNN, et nous concevons des expériences synthétiques pour montrer leur impact. Alors que les fonctions proposées montrent des améliorations par rapport à un modèle de base non modifié dans des scénarios synthétiques spécifiques et stricts, l'impact sur des scénarios plus généraux est moins significatif. Ce résultat n'est pas facile à expliquer, car l'entrainement des réseaux neuronaux est un processus opaque, et une exploration plus approfondie est nécessaire pour comprendre comment un CNN apprend (ou n'apprend pas) à raisonner en utilisant des informations relationnelles.Pour mieux comprendre comment un CNN peut apprendre à raisonner en utilisant des informations relationnelles, nous proposons un large éventail d'expériences synthétiques. Nous explorons les processus qui permettent, facilitent ou entravent le raisonnement "standard" des CNN sur les relations. Nous proposons une expérience fondamentale pour démontrer qu'un CNN de base, non modifié, est capable de raisonner sur les relations dans certains scénarios. Ensuite, nous explorons quelles relations sont apprises par le CNN, en effectuant l'inférence sur des scènes où les relations a priori sont perturbées, en comparant les résultats, et en entraînant et testant les CNN sur des données synthétiques avec plus ou moins de relations disponibles. Nous étudions ensuite les limites posées au raisonnement relationnel par le champ réceptif du réseau, et approfondissons notre analyse sur des situations où la quantité de données d'entraînement est insuffisante. Enfin, nous examinons à quel moment de la formation les relations sont satisfaites, ce qui permet de comprendre à quel moment les relations elles-mêmes sont apprises.En suivant une approche de groupement de noeuds dans des graphes pour l'utilisation des informations relationnelles, nous utilisons les relations dans un contexte d'apprentissage automatique différent, celui de la découverte de communautés dans des graphes. Nous formulons le groupement dans des graphes comme un problème de correspondance inexacte entre le graphe à analyser et un graphe modèle qui encode les connaissances a priori sur la façon dont les communautés ou les clusters sont liés les uns aux autres. Nous comparons cette approche avec les approches traditionnelles de groupement dans des graphes sur un ensemble de graphes synthétiques, pour mettre en évidence les avantages d'une approche relationnelle, ainsi que sur des graphes réels
This thesis studies the capabilities of machine learning methods for reasoning on spatial relationships, with a particular focus on directional relationships, and the use of prior relational information by these methods. There are many works in the field of applying knowledge on relationships to machine learning methods. However, this body of work still leaves several open questions. Throughout this thesis, we explore, investigate and attempt to explain different research questions linked to this field.We propose an improvement to the training of CNNs via a regularisation loss function based on relational information. To this end, we propose two novel loss functions which reward relationship satisfaction during CNN training, and design synthetic experiments to showcase their impact. While the proposed loss functions show improvements over an unmodified baseline in specific, strict synthetic scenarios, the impact on more ``generic'' training scenarios is less significant. This result is not easily explainable, as neural network training is a significantly opaque process, and as such, a deeper exploration is required to understand how a CNN learns (or fails to learn) to reason using relational information.To further understanding of how a CNN can learn to reason using relational information, we propose a wide array of distinct synthetic experiments. We explore the processes which enable, facilitate, or hinder ``standard'' CNN reasoning on relationships. We propose a fundamental experience to demonstrate that a basic, unmodified CNN is capable of relational reasoning in some scenarios. Next, we explore which relationships are learned by the CNN, by performing inference on scenes where the prior relationships are disturbed, by recording the difference in the results, and by training and testing CNNs on synthetic data with more or less relationships available. We then investigate the limits placed on relational reasoning by the network receptive field, as well as deepen our analysis on situations where the amount of training data is insufficient. Finally, we explore at which moment during training relationships are satisfied, as a proxy for understanding at which moment the relationships themselves are learned.Following a graph-clustering approach to the usage of relational information, we explore prior relationships in a different machine learning context, that of community discovery on graphs. We formulate graph clustering as an inexact matching problem between the graph to be clustered and a model graph which encodes prior knowledge on how the communities or clusters relate to each other. We compare this approach with traditional graph clustering approaches on a set of synthetic graphs, to showcase the advantages of a relational-aware approach, as well as on real graphs

Cette thèse de doctorat porte sur l’analyse de réseaux pondérés, graphes finis où chaque arête est associée à un poids représentant l’intensité de sa force. Nous introduisons une extension du modèle à blocs stochastiques (SBM) binaire, appelée modèle à blocs stochastiques binomial (bSBM). Cette question est motivée par l’étude des réseaux de co-citations dans un contexte de fouille de textes où les données sont représentées par un graphe. Les noeuds sont des mots et chaque arête joignant deux mots est pondérée par le nombre de documents inclus dans le corpus citant simultanément cette paire de mots. Nous développons une méthode d’inférence basée sur l’algorithme espérance maximisation variationnel (EMV) pour estimer les paramètres du modèle proposé ainsi que pour classifier les mots du réseau. Puis nous adoptons une méthode qui repose sur la maximisation d’un critère ICL (en anglais integrated classification likelihood) pour sélectionner le modèle optimal et le nombre de clusters. D’autre part, nous développons une approche variationnelle pour traiter le réseau et nous comparons les deux approches. Des applications à des données réelles sont adoptées pour montrer l’efficacité des deux méthodes ainsi que pour les comparer. Enfin, nous développons un SBM avec plusieurs attributs pour traiter les réseaux ayant des poids associés aux noeuds. Nous motivons cette méthode par une application qui vise au développement d’un outil d’aide à la spécification de différents traitements cognitifs réalisés par le cerveau lors de la préparation à l’écriture
This PhD thesis focuses on the analysis of weighted networks, where each edge is associated to a weight representing its strength. We introduce an extension of the binary stochastic block model (SBM), called binomial stochastic block model (bSBM). This question is motivated by the study of co-citation networks in a context of text mining where data is represented by a graph. Nodes are words and each edge joining two words is weighted by the number of documents included in the corpus simultaneously citing this pair of words. We develop an inference method based on a variational maximization algorithm (VEM) to estimate the parameters of the modelas well as to classify the words of the network. Then, we adopt a method based on maximizing an integrated classification likelihood (ICL) criterion to select the optimal model and the number of clusters. Otherwise, we develop a variational approach to analyze the given network. Then we compare the two approaches. Applications based on real data are adopted to show the effectiveness of the two methods as well as to compare them. Finally, we develop a SBM model with several attributes to deal with node-weighted networks. We motivate this approach by an application that aims at the development of a tool to help the specification of different cognitive treatments performed by the brain during the preparation of the writing

Dans le domaine de la biologie développementale, un des principaux défis est de comprendre comment des tissus multicellulaires, à l'origine indifférenciés, peuvent engendrer des formes aussi complexes que celles d'une fleur. De part son implication dans l'organogenèse florale, l'auxine est une phytohormone majeure. Nous avons donc déterminé son réseau binaire potentiel, puis y avons appliqué des modèles de clustering de graphes s'appuyant sur les profils de connexion présentés par ces 52 facteurs de transcription (FT). Nous avons ainsi pu identifier trois groupes, proches des groupes biologiques putatifs: les facteurs de réponse à l'auxine activateurs (ARF+), répresseurs (ARF-) et les Aux/IAAs. Nous avons détecté l'auto-interaction des ARF+ et des Aux/IAA, ainsi que leur interaction, alors que les ARF- en présentent un nombre restreint. Ainsi, nous proposons un mode de compétition auxine indépendent entre ARF+ et ARF- pour la régulation transcriptionelle. Deuxièmement, nous avons modélisé l'influence des séquences de dimérisation des FT sur la structure de l'interactome en utilisant des modèles de mélange Gaussien pour graphes aléatoires. Les groupes obtenus sont proches des précédents, et les paramètres estimés nous on conduit à conclure que chaque sous-domaine peut jouer un rôle différent en fonction de leur proximité phylogénétique.Enfin, nous sommes passés à l'échelle multi-cellulaire ou, par un graphe spatio-temporel, nous avons modélisé les premiers stades du développement floral d'A. thaliana. Nous avons pu extraire des caractéristiques cellulaires (3D+t) de reconstruction d'imagerie confocale, et avons démontré la possibilité de caractériser l'identité cellulaire en utilisant des méthodes de classification hiérarchique et des arbres de Markov cachés
A striking aspect of flowering plants is that, although they seem to display a great diversity of size and shape, they are made of the same basics constituents, that is the cells. The major challenge is then to understand how multicellular tissues, originally undifferentiated, can give rise to such complex shapes. We first investigated the uncharacterised signalling network of auxin since it is a major phytohormone involved in flower organogenesis.We started by determining the potential binary network, then applied model-based graph clustering methods relying on connectivity profiles. We demonstrated that it could be summarise in three groups, closely related to putative biological groups. The characterisation of the network function was made using ordinary differential equation modelling, which was later confirmed by experimental observations.In a second time, we modelled the influence of the protein dimerisation sequences on the auxin interactome structure using mixture of linear models for random graphs. This model lead us to conclude that these groups behave differently, depending on their dimerisation sequence similarities, and that each dimerisation domains might play different roles.Finally, we changed scale to represent the observed early stages of A. thaliana flower development as a spatio-temporal property graph. Using recent improvements in imaging techniques, we could extract 3D+t cellular features, and demonstrated the possibility of identifying and characterising cellular identity on this basis. In that respect, hierarchical clustering methods and hidden Markov tree have proven successful in grouping cell depending on their feature similarities

Cette thèse s’intéresse aux réseaux de confusion comme représentation compacte et structurée des hypothèses multiples produites par un moteur de reconnaissance de parole et transmises à un module de post-traitement applicatif. Les réseaux de confusion (CN pour Confusion Networks) sont générés à partir des graphes de mots et structurent l’information sous la forme d’une séquence de classes contenant des hypothèses de mots en concurrence. Le cas d’usage étudié dans ces travaux est celui des hypothèses de reconnaissance transmises à un module de compréhension de la parole dans le cadre d’une application de dialogue déployée par France Telecom. Deux problématiques inhérentes à ce contexte applicatif sont soulevées. De façon générale, un système de dialogue doit non seulement reconnaître un énoncé prononcé par un utilisateur, mais aussi l’interpréter afin de déduire sons sens. Du point de vue de l’utilisateur, les performances perçues sont plus proches de celles de la chaîne complète de compréhension que de celles de la reconnaissance vocale seule. Ce sont ces performances que nous cherchons à optimiser. Le cas plus particulier d’une application déployée implique de pouvoir traiter des données réelles et donc très variées. Un énoncé peut être plus ou moins bruité, dans le domaine ou hors-domaine, couvert par le modèle sémantique de l’application ou non, etc. Étant donnée cette grande variabilité, nous posons la question de savoir si le fait d’appliquer les mêmes traitements sur l’ensemble des données, comme c’est le cas dans les approches classiques, est une solution adaptée. Avec cette double perspective, cette thèse s’attache à la fois à enrichir l’algorithme de construction des CNs dans le but d’optimiser globalement le processus de compréhension et à proposer une stratégie adéquate d’utilisation des réseaux de confusion dans le contexte d’une application réelle. Après une analyse des propriétés de deux approches de construction des CNs sur un corpus de données réelles, l’algorithme retenu est celui du "pivot". Nous en proposons une version modifiée et adaptée au contexte applicatif en introduisant notamment un traitement différencié des mots du graphe qui privilégie les mots porteurs de sens. En réponse à la grande variabilité des énoncés à traiter dans une application déployée, nous proposons une stratégie de décision à plusieurs niveaux qui vise à mieux prendre en compte les spécificités des différents types d’énoncés. Nous montrons notamment qu’il est préférable de n’exploiter la richesse des sorties multiples que sur les énoncés réellement porteurs de sens. Cette stratégie permet à la fois d’optimiser les temps de calcul et d’améliorer globalement les performances du système
The work presented in this PhD deals with the confusion networks as a compact and structured representation of multiple aligned recognition hypotheses produced by a speech recognition system and used by different applications. The confusion networks (CN) are constructed from word graphs and structure information as a sequence of classes containing several competing word hypothesis. In this work we focus on the problem of robust understanding from spontaneous speech input in a dialogue application, using CNs as structured representation of recognition hypotheses for the spoken language understanding module. We use France Telecom spoken dialogue system for customer care. Two issues inherent to this context are tackled. A dialogue system does not only have to recognize what a user says but also to understand the meaning of his request and to act upon it. From the user’s point of view, system performance is more accurately represented by the performance of the understanding process than by speech recognition performance only. Our work aims at improving the performance of the understanding process. Using a real application implies being able to process real heterogeneous data. An utterance can be more or less noisy, in the domain or out of the domain of the application, covered or not by the semantic model of the application, etc. A question raised by the variability of the data is whether applying the same processes to the entire data set, as done in classical approaches, is a suitable solution. This work follows a double perspective : to improve the CN construction algorithm with the intention of optimizing the understanding process and to propose an adequate strategy for the use of CN in a real application. Following a detailed analysis of two CN construction algorithms on a test set collected using the France Telecom customer care service, we decided to use the "pivot" algorithm for our work. We present a modified and adapted version of this algorithm. The new algorithm introduces different processing techniques for the words which are important for the understanding process. As for the variability of the real data the application has to process, we present a new multiple level decision strategy aiming at applying different processing techniques for different utterance categories. We show that it is preferable to process multiple recognition hypotheses only on utterances having a valid interpretation. This strategy optimises computation time and yields better global performance