Dissertationen zum Thema „Graphes relationnels“

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 presentons dans ce memoire une nouvelle methode de reconnaissance des formes basee sur des concepts flous et des notions de theorie des graphes. Dans un premier temps, nous realisons une phase de segmentation floue qui transforme l'image de depart en un ensemble de regions floues. Puis nous decomposons chaque region floue en un ensemble de regions classiques. Nous calculons ensuite des attributs topologiques et relationnels sur ces regions. Nous combinons ceux-ci de maniere a obtenir, pour chaque caracteristique, un apercu general de la region floue. Nous obtenons ainsi une description de l'image sous la forme d'un graphe multivalue. A ce niveau, nous avons developpe trois types de recherches d'objets dont la complexite est croissante. Nous avons traite le cas d'une recherche d'objets atomiques simples avec une application sur des images astronomiques. Puis nous nous sommes orientes sur le probleme de la recherche d'arbres isomorphes. Ces derniers sont decrits de maniere hierarchique au sens de l'inclusion des regions. Nous avons propose a ce niveau une nouvelle methode de compression d'arbres etiquetes, basee sur la notion de graphes orientes sans circuit, pour accelerer le processus de recherche. Enfin, nous nous sommes interesses a des algorithmes de recherche par isomorphisme sur des graphes, en tenant compte des attributs relationnels. Nous avons aussi propose une nouvelle methode, basee sur la notion d'histogramme d'angles et de forces, pour calculer des relations de type directionnel. Ces relations donnent une information plus substantielle lors de l'appariement et permettent ainsi une decision plus sure

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

Cette thèse se concentre sur l'intégration des connaissances d'experts pour améliorer le raisonnement dans l'incertitude. Notre objectif est de guider l'apprentissage des relations probabilistes avec les connaissances d'experts pour des domaines décrits par les ontologies.Pour ce faire, nous proposons de coupler des bases de connaissances (BC) et une extension orientée objet des réseaux bayésiens, les modèles relationnels probabilistes (PRM). Notre objectif est de compléter l'apprentissage statistique par des connaissances expertes afin d'apprendre un modèle aussi proche que possible de la réalité et de l'analyser quantitativement (avec des relations probabilistes) et qualitativement (avec la découverte causale). Nous avons développé trois algorithmes à travers trois approches distinctes, dont les principales différences résident dans leur automatisation et l'intégration (ou non) de la supervision d'experts humains.L'originalité de notre travail est la combinaison de deux philosophies opposées : alors que l'approche bayésienne privilégie l'analyse statistique des données fournies pour raisonner avec, l'approche ontologique est basée sur la modélisation de la connaissance experte pour représenter un domaine. La combinaison de la force des deux permet d'améliorer à la fois le raisonnement dans l'incertitude et la connaissance experte
This thesis focuses on integrating expert knowledge to enhance reasoning under uncertainty. Our goal is to guide the probabilistic relations’ learning with expert knowledge for domains described by ontologies.To do so we propose to couple knowledge bases (KBs) and an oriented-object extension of Bayesian networks, the probabilistic relational models (PRMs). Our aim is to complement the statistical learning with expert knowledge in order to learn a model as close as possible to the reality and analyze it quantitatively (with probabilistic relations) and qualitatively (with causal discovery). We developped three algorithms throught three distinct approaches, whose main differences lie in their automatisation and the integration (or not) of human expert supervision.The originality of our work is the combination of two broadly opposed philosophies: while the Bayesian approach favors the statistical analysis of the given data in order to reason with it, the ontological approach is based on the modelization of expert knowledge to represent a domain. Combining the strenght of the two allows to improve both the reasoning under uncertainty and the expert knowledge

Cette dernière décennie, la modélisation des villes 3D est devenue l'un des enjeux de la recherche multimédia et un axe important en reconnaissance d'objets. Dans cette thèse nous nous sommes intéressés à localiser différentes primitives, plus particulièrement les fenêtres, dans les façades de Paris. Dans un premier temps, nous présentons une analyse des façades et des différentes propriétés des fenêtres. Nous en déduisons et proposons ensuite un algorithme capable d'extraire automatiquement des hypothèses de fenêtres. Dans une deuxième partie, nous abordons l'extraction et la reconnaissance des primitives à l'aide d'appariement de graphes de contours. En effet une image de contours est lisible par l'oeil humain qui effectue un groupement perceptuel et distingue les entités présentes dans la scène. C'est ce mécanisme que nous avons cherché à reproduire. L'image est représentée sous la forme d'un graphe d'adjacence de segments de contours, valué par des informations d'orientation et de proximité des segments de contours. Pour la mise en correspondance inexacte des graphes, nous proposons plusieurs variantes d'une nouvelle similarité basée sur des ensembles de chemins tracés sur les graphes, capables d'effectuer les groupements des contours et robustes aux changements d'échelle. La similarité entre chemins prend en compte la similarité des ensembles de segments de contours et la similarité des régions définies par ces chemins. La sélection des images d'une base contenant un objet particulier s'effectue à l'aide d'un classifieur SVM ou kppv. La localisation des objets dans l'image utilise un système de vote à partir des chemins sélectionnés par l'algorithme d'appariement
This last decade, modeling of 3D city became one of the challenges of multimedia search and an important focus in object recognition. In this thesis we are interested to locate various primitive, especially the windows, in the facades of Paris. At first, we present an analysis of the facades and windows properties. Then we propose an algorithm able to extract automatically window candidates. In a second part, we discuss about extraction and recognition primitives using graph matching of contours. Indeed an image of contours is readable by the human eye, which uses perceptual grouping and makes distinction between entities present in the scene. It is this mechanism that we have tried to replicate. The image is represented as a graph of adjacency of segments of contours, valued by information orientation and proximity to edge segments. For the inexact matching of graphs, we propose several variants of a new similarity based on sets of paths, able to group several contours and robust to scale changes. The similarity between paths takes into account the similarity of sets of segments of contours and the similarity of the regions defined by these paths. The selection of images from a database containing a particular object is done using a KNN or SVM classifier

L'idée d'établir des relations entre des objets et de les représenter dans la base de connaissances d'un système informatique est le propre de toute approche en Intelligence Artificielle. Cependant, la plupart des formalismes de représentation de connaissances n'exploitent pas toute la richesse de la sémantique de ces relations, ni le comportement qui leur est associé. En recherche d'informations, les traitements de ces relations ne sont guère mieux élaborés et l'impact de leur prise en compte lors de la phase de correspondance n'a jamais été établi, même s'il reste vrai que de nombreuses approches tiennent compte de leur présence dans le document et tentent ainsi de les représenter lors du processus d'indexation. Pourtant la recherche de documents structurés ou complexes exige plus que jamais, outre un langage d'indexation robuste et expressif, la prise en charge de la sémantique des relations ainsi que leurs propriétés. À travers une étude des nouvelles exigences auxquelles la recherche d'informations d'aujourd'hui doit répondre, nous proposons un modèle d'indexation relationnel pour les documents. L'approche consiste à considérer qu'un terme d'indexation est fondé sur des concepts complexes où les connecteurs sémantiques sont vus comme des opérateurs, ou des relations permettant de construire des expressions nouvelles représentant des concepts nouveaux ou des situations nouvelles. Le modèle proposé ne se contente pas de représenter les relations, mais permet aussi d'offrir un cadre général précisant les principes généraux de manipulation de ces relations et la prise en compte de leurs propriétés dans un processus de recherche fondé sur une approche logique. Le modèle proposé comporte deux composantes: le langage de représentation des informations, permettant une approche d'indexation relationnelle, et les règles de dérivation qui, reprenant ce langage, permettent de diriger le processus de correspondance. Nous utilisons la théorie des situations comme langage de représentation et un système de dérivation de pertinence, reposant sur une axiomatisation de la notion de correspondance entre les documents et la requête pour la prise en compte des relations. Une caractéristique intéressante de ce modèle est qu'il conduit à étendre certains formalismes de représentation de connaissances par des notions utiles en recherche d'informations. Les limitations de la famille des logiques terminologiques, utilisée par ailleurs comme base formelle de l'approche d'indexation relationnelle proposée, peuvent ainsi être surmontées. Cependant, la complexité des traitements associés à cette famille de logiques empêche de les utiliser comme un modèle opérationnel. Nous proposons alors le formalisme des graphes conceptuels comme un bon compromis entre la complexité des démonstrateurs de théorèmes et la simplicité des approches algébriques. Ce formalisme est alors vu, à travers une interprétation logique adéquate, comme une implantation d'une logique terminologique étendue et du modèle d'indexation. Notre approche a été implantée sur une plate-forme de gestion de graphes conceptuels, réalisée sur le système de gestion de base de données à objets O2. Le prototype RELIEF résultant de notre expérimentation a été testé sur une collection d'images et a démontré l'applicabilité et le bien-fondé de notre approche.

Il n’est plus à prouver que le numérique, Internet et le web ont entraîné une révolution notamment dans la manière de s’informer. Comme toute révolution, elle est suivie par une série d’enjeux : égalité de traitement des utilisateurs et des fournisseurs, consommations écologiquement durables, liberté d’expression et censure, etc. Il est nécessaire que la recherche apporte une vision claire de ces enjeux. Parmi ces enjeux, nous pouvons parler de deux phénomènes : le phénomène de chambre d’écho et le phénomène de bulle de filtre. Ces deux phénomènes sont liés au manque de diversité de l’information visible sur internet, et on peut se demander l’impact des algorithmes de recommandations. Même si ceci est notre motivation première, nous nous éloignons de ce sujet pour proposer un cadre scientifique général pour analyser la diversité. Nous trouvons que le formalisme de graphe est assez utile pour pouvoir représenter des données relationnelles. Plus précisément, nous allons analyser des données relationnelles avec des entités de différentes natures. C’est pourquoi nous avons choisi le formalisme de graphe n-partie car c’est une bonne manière de représenter une grande diversité de données. Même si nos premières données étudiées seront en lien avec les algorithmes de recommandation (consommation musicale ou achat d’article sur une plateforme) nous allons voir au fil du manuscrit en quoi ce formalisme peut être adapté à d’autres types de données (utilisateurs politisés sur Twitter, invités d’émissions de télévision, installation d’ONG dans différents États...). Il y a plusieurs objectifs dans cette étude : — Définir mathématiquement des indicateurs de diversité sur les graphes n-parties. — Définir algorithmiquement comment les calculer. — Programmer ces algorithmes pour en faire un objet informatique utilisable. — Utiliser ces programmes sur des données assez variées. — Voir les sens différents que nos indicateurs peuvent avoir. Nous commencerons par décrire le formalisme mathématique nécessaire à notre étude. Puis nous appliquerons notre objet mathématique à des exemples de base pour y voir toutes les possibilités que notre objet nous offre. Ceci nous montrera l’importance de normaliser nos indicateurs, et nous motivera à étudier une normalisation par l’aléatoire. Ensuite nous verrons une autre série d’exemples qui nous permettrons d’aller plus loin sur nos indicateurs, en dépassant le coté statique et tripartie pour aborder des graphes avec plus de couches et dépendant du temps. Pour pouvoir avoir une meilleure vision de ce que les données réelles nous apportent, nous étudierons nos indicateurs sur des graphes complètement générés aléatoirement
There is no longer any need to prove that digital technology, the Internet and the web have led to a revolution, particularly in the way people get information. Like any revolution, it is followed by a series of issues : equal treatment of users and suppliers, ecologically sustainable consumption, freedom of expression and censorship, etc. Research needs to provide a clear vision of these stakes. Among these issues, we can talk about two phenomena : the echo chamber phenomenon and the filter bubble phenomenon. These two phenomena are linked to the lack of diversity of information visible on the Internet, and one may wonder about the impact of recommendation algorithms. Even if this is our primary motivation, we are moving away from this subject to propose a general scientific framework to analyze diversity. We find that the graph formalism is useful enough to be able to represent relational data. More precisely, we will analyze relational data with entities of different natures. This is why we chose the n-part graph formalism because this is a good way to represent a great diversity of data. Even if the first data we studied is related to recommendation algorithms (music consumption or purchase of articles on a platform) we will see over the course of the manuscript how this formalism can be adapted to other types of data (politicized users on Twitter, guests of television shows, establishment of NGOs in different States ...). There are several objectives in this study : — Mathematically define diversity indicators on the n-part graphs. — Algorithmically define how to calculate them. — Program these algorithms to make them a usable computer object. — Use these programs on quite varied data. — See the different meanings that our indicators can have. We will begin by describing the mathematical formalism necessary for our study. Then we will apply our mathematical object to basic examples to see all the possibilities that our object offers us. This will show us the importance of normalizing our indicators, and will motivate us to study random normalization. Then we will see another series of examples which will allow us to go further on our indicators, going beyond the static and tripartite side to approach graphs with more layers and depending on time. To be able to have a better vision of what the real data brings us, we will study our indicators on completely randomly generated graphs

Cette dernière décennie, la modélisation des villes 3D est devenue l'un des enjeux de la recherche multimédia et un axe important en reconnaissance d'objets. Dans cette thèse nous nous sommes intéressés à localiser différentes primitives, plus particulièrement les fenêtres, dans les façades de Paris. Dans un premier temps, nous présentons une analyse des façades et des différentes propriétés des fenêtres. Nous en déduisons et proposons ensuite un algorithme capable d'extraire automatiquement des hypothèses de fenêtres. Dans une deuxième partie, nous abordons l'extraction et la reconnaissance des primitives à l'aide d'appariement de graphes de contours. En effet une image de contours est lisible par l'oeil humain qui effectue un groupement perceptuel et distingue les entités présentes dans la scène. C'est ce mécanisme que nous avons cherché à reproduire. L'image est représentée sous la forme d'un graphe d'adjacence de segments de contours, valué par des informations d'orientation et de proximité des segments de contours. Pour la mise en correspondance inexacte des graphes, nous proposons plusieurs variantes d'une nouvelle similarité basée sur des ensembles de chemins tracés sur les graphes, capables d'effectuer les groupements des contours et robustes aux changements d'échelle. La similarité entre chemins prend en compte la similarité des ensembles de segments de contours et la similarité des régions définies par ces chemins. La sélection des images d'une base contenant un objet particulier s'effectue à l'aide d'un classifieur SVM ou kppv. La localisation des objets dans l'image utilise un système de vote à partir des chemins sélectionnés par l'algorithme d'appariement.

La thèse contribue à l’étude du λ-calcul non-typé de Church, un système de réécriture dont la règle principale est la β-réduction (formalisant l’exécution d’un programme). Nous nous concentrons sur la sémantique dénotationnelle, l’étude de modèles du λ-calcul interprétant de la même façon les λ-termes β-convertibles. On examine la sémantique relationnelle, une sémantique sensible aux ressources qui interprète les λ-termes comme des relations avec les entrées regroupées en multi-ensembles. Nous définissons une classe de modèles relationnels, les modèles de graphe relationnels (rgm’s), que nous étudions avec une approche issue de la théorie des types et de la démonstration, par le biais de certains systèmes de types avec intersection non-idémpotente. D’abord, nous découvrons la plus petite et la plus grande λ–théorie (théorie équationnelle étendant la β-conversion) représentées dans la classe. Ensuite, nous utilisons les rgm’s afin de résoudre le problème de l’adéquation complète pour la λ–théorie observationnelle de Morris, à savoir l’équivalence contextuelle de programmes que l’on obtient lorsqu’on prend les β-formes normales comme sorties observables. On résoudre le problème de différentes façons. En caractérisant la β-normalisabilité avec les types, nous découvrons une infinité de rgm’s complètement adéquats, que nous appelons uniformément sans fond. Puis, nous résolvons le problème de façon exhaustive, en prouvant qu’un rgm est complètement adéquat pour l’observabilité de Morris si et seulement si il est extensionnel (il modèle l’ŋ-conversion) et λ-König. Moralement un rgm est λ-König si tout arbre récursif infini a une branche infinie témoignée par un type non-bien-fondé
This thesis is a contribution to the study of Church’s untyped λ-calculus, a term rewritingsystem having the β-reduction (the formal counterpart of the idea of execution of programs) asmain rule. The focus is on denotational semantics, namely the investigation of mathematical models of the λ-calculus giving the same denotation to β-convertible λ-terms. We investigate relational semantics, a resource-sensitive semantics interpreting λ-terms as relations,with their inputs grouped together in multisets. We define a large class of relational models,called relational graph models (rgm’s), and we study them in a type/proof-theoretical way, using some non-idempotent intersection type systems. Firstly, we find the minimal and maximal λ-theories (equational theories extending -conversion) represented by the class.Then we use rgm’s to solve the full abstraction problem for Morris’s observational λ-theory,the contextual equivalence of programs that one gets by taking the β-normal forms asobservable outputs. We solve the problem in different ways. Through a type-theoretical characterization of β-normalizability, we find infinitely many fully abstract rgm’s, that wecall uniformly bottomless.We then give an exhaustive answer to the problem, by showing thatan rgm is fully abstract for Morris’s observability if and only if it is extensional (a model of ŋ-conversion) and λ-König. Intuitively an rgm is λ-König when every infinite computable tree has an infinite branch witnessed by some type of the model, where the witnessing is a property of non-well-foundedness on the type

Dans ce travail nous proposons une interface d'interrogation graphique des bases de donnees: ruitalk. Le schema de la base est modelise par un graphe semantique normalise. Ce graphe est le schema de donnees dans le modele relation universelle avec inclusions (rui). Il herite de la rigueur du modele relationnel de donnees et est plus riche semantiquement qu'un diagramme entite-association. Il visualise un certain nombre de rapprochements naturels entre tables d'une base de donnees: multiarcs de dependance d'inclusion (di) et arcs d'attributs communs univoques. Nous completons ce graphe en explicitant tous les rapprochements possibles entre relations du graphe semantique: aretes d'attributs communs, eclatements de di entre les relations normalisees. Nous montrons aussi que des attributs compatibles sont a la source de liens semantiques entre relations supplementaires. Ruitalk reste convival et ergonomique bien que le nombre de liens de jointures possibles entre relations peut etre grand. En effet, il ne genere pas simultanement tous ces liens, mais il affiche un graphe d'interrogation evolutif, accompagnant l'avancement de l'utilisateur dans le processus d'expression d'une question. Ce graphe visualise, en plus du graphe semantique normalise binaire, pour le sommet designe par l'utilisateur, ses liens avec chaque autre sommet. L'utilisateur est assiste au maximum dans la formulation de ses requetes par ruitalk. Il a a tout moment devant les yeux le schema des donnees. Pour definir le graphe de sa requete, il n'a qu'a designer les colonnes a projeter et les liens du graphe d'interrogation evolutif representant une jointure. Il peut aussi facilement specifier des predicats de selection et des sous-requetes. Il est constamment guide par le support graphique de ruitalk

Un graphe étant un ensemble d'objets liés par une certaine relation typée, le problème de "modularisation" des grands graphes (qui revient à leur partitionnement en classes) peut, alors, être modélisé mathématiquement en utilisant l'Analyse Relationnelle. Cette modélisation permet de comparer sur les mêmes bases un certain nombre de critères de découpage de graphe c'est-à-dire de modularisation. Nous proposons une réécriture Relationnelle des critères de modularisation connus tels le critère de Newman-Girvan, Zahn-Condorcet, Owsinski-Zadrozny, Condorcet pondéré, Demaine-Immorlica, Wei-Cheng, la Différence de profils et Michalski-Goldberg. Nous introduisons trois critères : la Modularité équilibrée, l'écart à l'Indétermination et l'écart à l'Uniformité. Nous identifions les propriétés vérifiées par ces critères et pour certains critères, notamment les critères linéaires, nous caractérisons les partitions obtenues via leur optimisation dans le but de faciliter leur compréhension et d'interpréter plus clairement leurs finalités en y associant la preuve de leur utilité dans certains contextes pratiques. Les résultats trouvés sont testés sur des graphes réels de tailles différentes avec l'algorithme de Louvain générique
Graphs are the mathematical representation of networks. Since a graph is a special type of binary relation, graph clustering (or modularization), can be mathematically modelled using the Mathematical Relational analysis. This modelling allows to compare numerous graph clustering criteria on the same type of formal representation. We give through a relational coding, the way of comparing different modularization criteria such as: Newman-Girvan, Zahn-Condorcet, Owsinski-Zadrozny, Demaine-Immorlica, Wei-Cheng, Profile Difference et Michalski-Goldberg. We introduce three modularization criteria: the Balanced Modularity, the deviation to Indetermination and the deviation to Uniformity. We identify the properties verified by those criteria and for some of those criteria, specially linear criteria, we characterize the partitions obtained by the optimization of these criteria. The final goal is to facilitate their understanding and their usefulness in some practical contexts, where their purposes become easily interpretable and understandable. Our results are tested by modularizing real networks of different sizes with the generalized Louvain algorithm

La représentation implicite de graphes a été introduite en 1966 par Breuer afin de calculer l'adjacence dans les graphes à partir de données locales encodées par chaque sommet. Dans ce document, on s'est intéressé à cette notion pour de nombreuses familles de graphes et en particulier pour les graphes sur surfaces. Afin de pouvoir utiliser les représentations implicites existantes sur les forêts, on montre tout d'abord l'existence d'une partition des arêtes des graphes de genre d'Euler g en trois forêts plus un ensemble d'au plus 3g - 3 arêtes. On présente une représentation implicite pour les arbres de degré interne borné par d̂ ayant n sommets avec des étiquettes de log n + O (log d̂) bits. Enfin, on décrit une représentation implicite pour les graphes planaires et les graphes de genre borné en (2 + 0(1)) log n bits déduite d'une représentation implicite pour les graphes de largeur arborescente bornée avec des étiquettes de (1 + 0(1)) log n bits. On utilise une technique similaire afin d'obtenir un schéma k-relationnel sur les arbres.

Avec la mondialisation, l'entreprise doit faire face aux menaces de plus en plus fortes de la concurrence et à l'accélération des flux d'information. Pour cela, elle est amenée à rester continuellement informée des innovations, des stratégies de la concurrence et de l'état du marché tout en gardant la maîtrise de son environnement. Le développement d'Internet et la globalisation ont à la fois renforcé cette exigence, et fourni les moyens de collecter l'information qui, une fois synthétisée, prend souvent une forme relationnelle. Pour analyser le relationnel, le recours à la visualisation par des graphes apporte un réel confort aux utilisateurs, qui, de façon intuitive, peuvent s'approprier une forme de connaissance difficile à appréhender autrement. Nos travaux conduisent à l'élaboration des techniques graphiques permettant la compréhension des activités humaines, de leurs interactions mais aussi de leur évolution, dans une perspective décisionnelle. Nous concevons un outil alliant simplicité d'utilisation et précision d'analyse se basant sur deux types de visualisations complémentaires : statique et dynamique. L'aspect statique de notre modèle de visualisation repose sur un espace de représentation, dans lequel les préceptes de la théorie des graphes sont appliqués. Le recours à des sémiologies spécifiques telles que le choix de formes de représentation, de granularité, de couleurs significatives permet une visualisation plus juste et plus précise de l'ensemble des données. L'utilisateur étant au cœur de nos préoccupations, notre contribution repose sur l'apport de fonctionnalités spécifiques, qui favorisent l'identification et l'analyse détaillée de structures de graphes. Nous proposons des algorithmes qui permettent de cibler le rôle des données au sein de la structure, d'analyser leur voisinage, tels que le filtrage, le k-core, la transitivité, de retourner aux documents sources, de partitionner le graphe ou de se focaliser sur ses spécificités structurelles. Une caractéristique majeure des données stratégiques est leur forte évolutivité. Or l'analyse statistique ne permet pas toujours d'étudier cette composante, d'anticiper les risques encourus, d'identifier l'origine d'une tendance, d'observer les acteurs ou termes ayant un rôle décisif au cœur de structures évolutives. Le point majeur de notre contribution pour les graphes dynamiques représentant des données à la fois relationnelles et temporelles, est le morphing de graphe. L'objectif est de faire ressortir les tendances significatives en se basant sur la représentation, dans un premier temps, d'un graphe global toutes périodes confondues puis en réalisant une animation entre les visualisations successives des graphes attachés à chaque période. Ce procédé permet d'identifier des structures ou des événements, de les situer temporellement et d'en faire une lecture prédictive. Ainsi notre contribution permet la représentation des informations, et plus particulièrement l'identification, l'analyse et la restitution des structures stratégiques sous jacentes qui relient entre eux et à des moments donnés les acteurs d'un domaine, les mots-clés et concepts qu'ils utilisent
With word wide exchanges, companies must face increasingly strong competition and masses of information flows. They have to remain continuously informed about innovations, competition strategies and markets and at the same time they have to keep the control of their environment. The Internet development and globalization reinforced this requirement and on the other hand provided means to collect information. Once summarized and synthesized, information generally is under a relational form. To analyze such a data, graph visualization brings a relevant mean to users to interpret a form of knowledge which would have been difficult to understand otherwise. The research we have carried out results in designing graphical techniques that allow understanding human activities, their interactions but also their evolution, from the decisional point of view. We also designed a tool that combines ease of use and analysis precision. It is based on two types of complementary visualizations: statics and dynamics. The static aspect of our visualization model rests on a representation space in which the precepts of the graph theory are applied. Specific semiologies such as the choice of representation forms, granularity, and significant colors allow better and precise visualizations of the data set. The user being a core component of our model, our work rests on the specification of new types of functionalities, which support the detection and the analysis of graph structures. We propose algorithms which make it possible to target the role of the data within the structure, to analyze their environment, such as the filtering tool, the k-core, and the transitivity, to go back to the documents, and to give focus on the structural specificities. One of the main characteristics of strategic data is their strong evolution. However the statistical analysis does not make it possible to study this component, to anticipate the incurred risks, to identify the origin of a trend, and to observe the actors or terms having a decisive role in the evolution structures. With regard to dynamic graphs, our major contribution is to represent relational and temporal data at the same time; which is called graph morphing. The objective is to emphasize the significant tendencies considering the representation of a graph that includes all the periods and then by carrying out an animation between successive visualizations of the graphs attached to each period. This process makes it possible to identify structures or events, to locate them temporally, and to make a predictive reading of it. Thus our contribution allows the representation of advanced information and more precisely the identification, the analysis, and the restitution of the underlying strategic structures which connect the actors of a domain, the key words, and the concepts they use; this considering the evolution feature

Avec la mondialisation, l'entreprise doit faire face aux menaces de plus en plus fortes de la concurrence et à l'accélération des flux d'information. Pour cela, elle est amenée à rester continuellement informée des innovations, des stratégies de la concurrence et de l'état du marché tout en gardant la maîtrise de son environnement. Le développement d'Internet et la globalisation ont à la fois renforcé cette exigence, et fourni les moyens de collecter l'information qui, une fois synthétisée, prend souvent une forme relationnelle. Pour analyser le relationnel, le recours à la visualisation par des graphes apporte un réel confort aux utilisateurs, qui, de façon intuitive, peuvent s'approprier une forme de connaissance difficile à appréhender autrement.
Nos travaux conduisent à l'élaboration des techniques graphiques permettant la compréhension des activités humaines, de leurs interactions mais aussi de leur évolution, dans une perspective décisionnelle. Nous concevons un outil alliant simplicité d'utilisation et précision d'analyse se basant sur deux types de visualisations complémentaires : statique et dynamique.
L'aspect statique de notre modèle de visualisation repose sur un espace de représentation, dans lequel les préceptes de la théorie des graphes sont appliqués. Le recours à des sémiologies spécifiques telles que le choix de formes de représentation, de granularité, de couleurs significatives permet une visualisation plus juste et plus précise de l'ensemble des données. L'utilisateur étant au cœur de nos préoccupations, notre contribution repose sur l'apport de fonctionnalités spécifiques, qui favorisent l'identification et l'analyse détaillée de structures de graphes. Nous proposons des algorithmes qui permettent de cibler le rôle des données au sein de la structure, d'analyser leur voisinage, tels que le filtrage, le k-core, la transitivité, de retourner aux documents sources, de partitionner le graphe ou de se focaliser sur ses spécificités structurelles.
Une caractéristique majeure des données stratégiques est leur forte évolutivité. Or l'analyse statistique ne permet pas toujours d'étudier cette composante, d'anticiper les risques encourus, d'identifier l'origine d'une tendance, d'observer les acteurs ou termes ayant un rôle décisif au cœur de structures évolutives.
Le point majeur de notre contribution pour les graphes dynamiques représentant des données à la fois relationnelles et temporelles, est le morphing de graphe. L'objectif est de faire ressortir les tendances significatives en se basant sur la représentation, dans un premier temps, d'un graphe global toutes périodes confondues puis en réalisant une animation entre les visualisations successives des graphes attachés à chaque période. Ce procédé permet d'identifier des structures ou des événements, de les situer temporellement et d'en faire une lecture prédictive.
Ainsi notre contribution permet la représentation des informations, et plus particulièrement l'identification, l'analyse et la restitution des structures stratégiques sous jacentes qui relient entre eux et à des moments donnés les acteurs d'un domaine, les mots-clés et concepts qu'ils utilisent.

La modélisation de la configuration spatiale des objets d’une image est un sujet encore peu abordé à ce jour, y compris dans les approches les plus modernes de vision par ordinateur comme les réseaux convolutionnels (CNN). Pourtant, il s’agit d’un aspect essentiel de la perception des scènes, et l’intégrer dans les modélisations devrait bénéficier à de nombreuses tâches du domaine, en contribuant à combler le "fossé sémantique" entre l’image numérique et l’interprétation de son contenu. Ainsi, cette thèse a pour objet l’amélioration des techniques de modélisation de la configuration spatiale, afin de l’exploiter dans des systèmes de description et de reconnaissance. Dans un premier temps, nous nous sommes penchés sur le cas de la configuration spatiale entre deux objets, en proposant une amélioration d’un descripteur existant. Ce nouveau descripteur appelé "bandeau de forces" est une extension de l’histogramme du même nom à tout un panel de forces, ce qui permet de mieux décrire les configurations complexes. Nous avons pu montrer son intérêt pour la description de scènes, en apprenant à classifier automatiquement des relations en langage naturel à partir de paires d’objets segmentés. Nous avons alors abordé la problématique du passage à des scènes comportant plusieurs objets, proposant une approche par objet en confrontant chaque objet à l’ensemble des autres, plutôt qu’en ayant un descripteur par paire. Dans un second temps, le contexte CIFRE nous a amenés à traiter une application au problème de la ré-identification de scènes ou d’objets, tâche qui s’apparente à la reconnaissance fine à partir de peu d’exemples. Pour cela, nous nous basons sur une approche traditionnelle en décrivant les constituants de la scène par différents descripteurs dédiés à des caractéristiques spécifiques, comme la couleur ou la forme, auxquelles nous ajoutons la configuration spatiale. La comparaison de deux scènes se fait alors en appariant leurs constituants grâce à ces caractéristiques, en utilisant par exemple l’algorithme hongrois. Différentes associations de caractéristiques peuvent être considérées pour l’appariement et pour le calcul du score final, selon les invariances présentes et recherchées. Pour chacun de ces deux sujets, nous avons été confrontés aux problèmes des données et de la segmentation. Nous avons alors généré et annoté un jeu de données synthétiques, et exploité deux jeux de données existants en les segmentant, dans deux cadres différents. La première approche concerne la segmentation objet-fond et se place dans le cas où une détection est disponible, ce qui permet d’aider la segmentation. Elle consiste à utiliser un modèle existant de segmentation globale, puis à exploiter la détection pour sélectionner le bon segment, à l’aide de plusieurs critères géométriques et sémantiques. La seconde approche concerne la décomposition d’une scène ou d’un objet en parties et se place dans le cas non supervisé. Elle se base alors sur la couleur des pixels, en utilisant une méthode par clustering dans un espace de couleur adapté, comme le cône HSV que nous avons utilisé. Tous ces travaux ont permis de montrer la possibilité d’utiliser la configuration spatiale pour la description de scènes réelles contenant plusieurs objets, ainsi que dans une chaîne de traitements complexe comme celle utilisée pour la ré-identification. En particulier, l’histogramme de forces a pu être utilisé pour cela, ce qui permet de profiter de ses bonnes performances, en utilisant une méthode de segmentation adaptée au cas d’usage pour traiter des images naturelles
Modeling the spatial configuration of objects in an image is a subject that is still little discussed to date, including in the most modern computer vision approaches such as convolutional neural networks ,(CNN). However, it is an essential aspect of scene perception, and integrating it into the models should benefit many tasks in the field, by helping to bridge the “semantic gap” between the digital image and the interpretation of its content. Thus, this thesis aims to improve spatial configuration modeling ,techniques, in order to exploit it in description and recognition systems. ,First, we looked at the case of the spatial configuration between two objects, by proposing an improvement of an existing descriptor. This new descriptor called “force banner” is an extension of the histogram of the same name to a whole range of forces, which makes it possible to better describe complex configurations. We were able to show its interest in the description of scenes, by learning toautomatically classify relations in natural language from pairs of segmented objects. We then tackled the problem of the transition to scenes containing several objects and proposed an approach per object by confronting each object with all the others, rather than having one descriptor per pair. Secondly, the industrial context of this thesis led us to deal with an application to the problem of re-identification of scenes or objects, a task which is similar to fine recognition from few examples. To do so, we rely on a traditional approach by describing scene components with different descriptors dedicated to specific characteristics, such as color or shape, to which we add the spatial configuration. The comparison of two scenes is then achieved by matching their components thanks to these characteristics, using the Hungarian algorithm for instance. Different combinations of characteristics can be considered for the matching and for the final score, depending on the present and desired invariances. For each one of these two topics, we had to cope with the problems of data and segmentation. We then generated and annotated a synthetic dataset, and exploited two existing datasets by segmenting them, in two different frameworks. The first approach concerns object-background segmentation and more precisely the case where a detection is available, which may help the segmentation. It consists in using an existing global segmentation model and exploiting the detection to select the right segment, by using several geometric and semantic criteria. The second approach concerns the decomposition of a scene or an object into parts and addresses the unsupervised case. It is based on the color of the pixels, by using a clustering method in an adapted color space, such as the HSV cone that we used. All these works have shown the possibility of using the spatial configuration for the description of real scenes containing several objects, as well as in a complex processing chain such as the one we used for re-identification. In particular, the force histogram could be used for this, which makes it possible to take advantage of its good performance, by using a segmentation method adapted to the use case when processing natural images

Notre travail porte sur l'extraction de connaissances sur des langages graphiques dont les symboles sont a priori inconnus. Nous formons l'hypothèse que l'observation d'une grande quantité de documents doit permettre de découvrir les symboles composant l'alphabet du langage considéré. La difficulté du problème réside dans la nature bidimensionnelle et manuscrite des langages graphiques étudiés. Nous nous plaçons dans le cadre de tracés en-ligne produit par des interfaces de saisie de type écrans tactiles, tableaux interactifs ou stylos électroniques. Le signal disponible est alors une trajectoire échantillonnée produisant une séquence de traits, eux-mêmes composés d'une séquence de points. Un symbole, élément de base de l'alphabet du langage, est donc composé d'un ensemble de traits possédant des propriétés structurelles et relationnelles spécifiques. L'extraction des symboles est réalisée par la découverte de sous-graphes répétitifs dans un graphe global modélisant les traits (noeuds) et leur relations spatiales (arcs) de l'ensemble des documents. Le principe de description de longueur minimum (MDL : Minimum Description Length) est mis en oeuvre pour choisir les meilleurs représentants du lexique des symboles. Ces travaux ont été validés sur deux bases expérimentales. La première est une base d'expressions mathématiques simples, la seconde représente des graphiques de type organigramme. Sur ces bases, nous pouvons évaluer la qualité des symboles extraits et comparer à la vérité terrain. Enfin, nous nous sommes intéressés à la réduction de la tâche d'annotation d'une base en considérant à la fois les problématiques de segmentation et d'étiquetage des différents traits.

L'explosion de données relationnelles largement disponiblessous la forme de graphes de connaissances a permisle développement de multiples applications, dont les agents personnels automatiques,les systèmes de recommandation et l'amélioration desrésultats de recherche en ligne.La grande taille et l'incomplétude de ces bases de donnéesnécessite le développement de méthodes de complétionautomatiques pour rendre ces applications viables.La complétion de graphes de connaissances, aussi appeléeprédiction de liens, se doit de comprendre automatiquementla structure des larges graphes de connaissances (graphes dirigéslabellisés) pour prédire les entrées manquantes (les arêtes labellisées).Une approche gagnant en popularité consiste à représenter ungraphe de connaissances comme un tenseur d'ordre 3, etd'utiliser des méthodes de décomposition de tenseur pourprédire leurs entrées manquantes.Les modèles de factorisation existants proposent différentscompromis entre leur expressivité, et leur complexité en temps et en espace.Nous proposons un nouveau modèle appelé ComplEx, pour"Complex Embeddings", pour réconcilier expressivité etcomplexité par l'utilisation d'une factorisation en nombre complexes,dont nous explorons le lien avec la diagonalisation unitaire.Nous corroborons notre approche théoriquement en montrantque tous les graphes de connaissances possiblespeuvent être exactement décomposés par le modèle proposé.Notre approche, basées sur des embeddings complexesreste simple, car n'impliquant qu'un produit trilinéaire complexe,là où d'autres méthodes recourent à des fonctions de compositionde plus en plus compliquées pour accroître leur expressivité.Le modèle proposé ayant une complexité linéaire en tempset en espace est passable à l'échelle, tout endépassant les approches existantes sur les jeux de données de référencepour la prédiction de liens.Nous démontrons aussi la capacité de ComplEx àapprendre des représentations vectorielles utiles pour d'autres tâches,en enrichissant des embeddings de mots, qui améliorentles prédictions sur le problème de traitement automatiquedu langage d'implication entre paires de phrases.Dans la dernière partie de cette thèse, nous explorons lescapacités de modèles de factorisation à apprendre lesstructures relationnelles à partir d'observations.De part leur nature vectorielle,il est non seulement difficile d'interpréter pourquoicette classe de modèles fonctionne aussi bien,mais aussi où ils échouent et comment ils peuventêtre améliorés. Nous conduisons une étude expérimentalesur les modèles de l'état de l'art, non pas simplementpour les comparer, mais pour comprendre leur capacitésd'induction. Pour évaluer les forces et faiblessesde chaque modèle, nous créons d'abord des tâches simplesreprésentant des propriétés atomiques despropriétés des relations des graphes de connaissances ;puis des tâches représentant des inférences multi-relationnellescommunes au travers de généalogies synthétisées.À partir de ces résultatsexpérimentaux, nous proposons de nouvelles directionsde recherches pour améliorer les modèles existants,y compris ComplEx
The explosion of widely available relational datain the form of knowledge graphsenabled many applications, including automated personalagents, recommender systems and enhanced web search results.The very large size and notorious incompleteness of these data basescalls for automatic knowledge graph completion methods to make these applicationsviable. Knowledge graph completion, also known as link-prediction,deals with automatically understandingthe structure of large knowledge graphs---labeled directed graphs---topredict missing entries---labeled edges. An increasinglypopular approach consists in representing knowledge graphs as third-order tensors,and using tensor factorization methods to predict their missing entries.State-of-the-art factorization models propose different trade-offs between modelingexpressiveness, and time and space complexity. We introduce a newmodel, ComplEx---for Complex Embeddings---to reconcile both expressivenessand complexity through the use of complex-valued factorization, and exploreits link with unitary diagonalization.We corroborate our approach theoretically and show that all possibleknowledge graphs can be exactly decomposed by the proposed model.Our approach based on complex embeddings is arguably simple,as it only involves a complex-valued trilinear product,whereas other methods resort to more and more complicated compositionfunctions to increase their expressiveness. The proposed ComplEx model isscalable to large data sets as it remains linear in both space and time, whileconsistently outperforming alternative approaches on standardlink-prediction benchmarks. We also demonstrateits ability to learn useful vectorial representations for other tasks,by enhancing word embeddings that improve performanceson the natural language problem of entailment recognitionbetween pair of sentences.In the last part of this thesis, we explore factorization models abilityto learn relational patterns from observed data.By their vectorial nature, it is not only hard to interpretwhy this class of models works so well,but also to understand where they fail andhow they might be improved. We conduct an experimentalsurvey of state-of-the-art models, not towardsa purely comparative end, but as a means to get insightabout their inductive abilities.To assess the strengths and weaknesses of each model, we create simple tasksthat exhibit first, atomic properties of knowledge graph relations,and then, common inter-relational inference through synthetic genealogies.Based on these experimental results, we propose new researchdirections to improve on existing models, including ComplEx

L’évolution et la démocratisation des technologies ont engendré une véritable explosion de l’information et notre capacité à générer des données et le besoin de les analyser n’a jamais été aussi important. Pourtant, les problématiques soulevées par l’accumulation de données (stockage, temps de traitement, hétérogénéité, vitesse de captation/génération, etc. ) sont d’autant plus fortes que les données sont massives, complexes et variées. La représentation de l’information, de part sa capacité à synthétiser et à condenser des données, se constitue naturellement comme une approche pour les analyser mais ne résout pas pour autant ces problèmes. En effet, les techniques classiques de visualisation sont rarement adaptées pour gérer et traiter cette masse d’informations. De plus,les problèmes que soulèvent le stockage et le temps de traitement se répercutent sur le système d’analyse avec par exemple, la distanciation de plus en plus forte entre la donnée et l’utilisateur : le lieu où elle sera stockée et traitée et l’interface utilisateur servant à l’analyse. Dans cette thèse nous nous intéressons à ces problématiques et plus particulièrement à l’adaptation des techniques de visualisation d’informations pour les données massives. Pour cela, nous nous intéressons tout d’abord à l’information de relation entre éléments, comment est-elle véhiculée et comment améliorer cette transmission dans le contexte de données hiérarchisées. Ensuite, nous nous intéressons à des données multivariées,dont la complexité à un impact sur les calculs possibles. Enfin, nous présentons les approches mises en oeuvre pour rendre nos méthodes compatibles avec les données massives
The evolution and spread of technologies have led to a real explosion of information and our capacity to generate data and our need to analyze them have never been this strong. Still, the problems raised by such accumulation (storage, computation delays, diversity, speed of gathering/generation, etc. ) is as strong as the data are big, complex and varied. Information visualization,by its ability to summarize and abridge data was naturally established as appropriate approach. However, it does not solve the problem raised by Big Data. Actually, classical visualization techniques are rarely designed to handle such mass of information. Moreover, the problems raised by data storage and computation time have repercussions on the analysis system. For example,the increasing distance between the data and the analyst : the place where the data is stored and the place where the user will perform the analyses arerarely close. In this thesis, we focused on these issues and more particularly on adapting the information visualization techniques for Big Data. First of all focus on relational data : how does the existence of a relation between entity istransmitted and how to improve this transmission for hierarchical data. Then,we focus on multi-variate data and how to handle their complexity for the required computations. Finally, we present the methods we designed to make our techniques compatible with Big Data

Le sujet de cette thèse s’inscrit dans le cadre général de la Recherche d’Information et la gestion des données massives et distribuées. Notre problématique concerne l’évaluation et l’optimisation de requêtes agrégatives (Aggregated Search). La Recherche d’Information Agrégative est un nouveau paradigme permettant l’accès à l’information massivement distribuée. Elle a pour but de retourner à l’utilisateur d’un système de recherche d’information des objets résultats qui sont riches et porteurs de connaissances. Ces objets n’existent pas en tant que tels dans les sources. Ils sont construits par assemblage (ou configuration ou agrégation) de fragments issus de diffèrentes sources. Les sources peuvent être non spécifiées dans l’expression de la requête mais découvertes dynamiquement lors de la recherche. Nous nous intéressons particulièrement à l’exploitation des dépendances de données pour optimiser les accès aux sources distribuées. Dans ce cadre, nous proposons une approche pour l’un des sous processus de systèmes de RIA, principalement le processus d’indexation/organisation des documents. Nous considérons dans cette thèse, les systèmes de recherche d’information orientés graphes (graphes RDF). Utilisant les relations dans les graphes, notre travail s’inscrit dans le cadre de la recherche d’information agrégative relationnelle (Relational Aggregated Search) où les relations sont exploitées pour agréger des fragments d’information. Nous proposons d’optimiser l’accès aux sources d’information dans un système de recherche d’information agrégative. Ces sources contiennent des fragments d’information répondant partiellement à la requête. L’objectif est de minimiser le nombre de sources interrogées pour chaque fragment de la requête, ainsi que de maximiser les opérations d’agrégations de fragments dans une même source. Nous proposons d’effectuer cela en réorganisant la/les base(s) de graphes dans plusieurs clusters d’information dédiés aux requêtes agrégatives. Ces clusters sont obtenus à partir d’une approche de clustering sémantique ou structurel des prédicats des graphes RDF. Pour le clustering structurel, nous utilisons les algorithmes d’extraction de sous-graphes fréquents et dans ce cadre nous élaborons une étude comparative des performances de ces algorithmes. Pour le clustering sémantique, nous utilisons les métadonnées descriptives des prédicats dont nous appliquons des outils de similarité textuelle sémantique. Nous définissons une approche de décomposition de requêtes basée essentiellement sur le clustering choisi
In this research, we are interested in investigating issues related to query evaluation and optimization in the framework of aggregated search. Aggregated search is a new paradigm to access massively distributed information. It aims to produce answers to queries by combining fragments of information from different sources. The queries search for objects (documents) that do not exist as such in the targeted sources, but are built from fragments extracted from the different sources. The sources might not be specified in the query expression, they are dynamically discovered at runtime. In our work, we consider data dependencies to propose a framework for optimizing query evaluation over distributed graph-oriented data sources. For this purpose, we propose an approach for the document indexing/orgranizing process of aggregated search systems. We consider information retrieval systems that are graph oriented (RDF graphs). Using graph relationships, our work is within relational aggregated search where relationships are used to aggregate fragments of information. Our goal is to optimize the access to source of information in a aggregated search system. These sources contain fragments of information that are relevant partially for the query. We aim at minimizing the number of sources to ask, also at maximizing the aggregation operations within a same source. For this, we propose to reorganize the graph database(s) in partitions, dedicated to aggregated queries. We use a semantic or strucutral clustering of RDF predicates. For structural clustering, we propose to use frequent subgraph mining algorithms, we performed for this, a comparative study of their performances. For semantic clustering, we use the descriptive metadata of RDF predicates and apply semantic textual similarity methods to calculate their relatedness. Following the clustering, we define query decomposing rules based on the semantic/structural aspects of RDF predicates

Historiquement, les Modèles Graphiques Probabilistes (PGMs) sont une solution d’apprentissage à partir des données incertaines et plates, appelées aussi données propositionnelles ou représentations attribut-valeur. Au début des années 2000, un grand intérêt a été adressé au traitement des données relationnelles présentant un grand nombre d’objets participant à des différentes relations. Les Modèles Probabilistes Relationnels (PRMs) présentent une extension des PGMs pour le contexte relationnel. Avec l’évolution rapide issue de l’internet, des innovations technologiques et des applications web, les données sont devenues de plus en plus variées et complexes. D’où l’essor du Big Data. Plusieurs types de bases de données ont été créés pour s’adapter aux nouvelles caractéristiques des données, dont les plus utilisés sont les bases de données graphe. Toutefois, tous les travaux d’apprentissage des PRMs sont consacrés à apprendre à partir des données bien structurées et stockées dans des bases de données relationnelles. Les bases de données graphe sont non structurées et n’obéissent pas à un schéma bien défini. Les arcs entre les noeuds peuvent avoir des différentes signatures. En effet, les relations qui ne correspondent pas à un modèle ER peuvent exister dans l'instance de base de données. Ces relations sont considérées comme des exceptions. Dans ce travail de thèse, nous nous intéressons à ce type de bases de données. Nous étudions aussi deux types de PRMs à savoir, Direct Acyclic Probabilistic Entity Relationship (DAPER) et chaines de markov logiques (MLNs). Nous proposons deux contributions majeures. Premièrement, Une approche d’apprentissage des DAPERs à partir des bases de données graphe partiellement structurées. Une deuxième approche consiste à exploiter la logique de premier ordre pour apprendre les DAPERs en utilisant les MLNs pour prendre en considération les exceptions qui peuvent parvenir lors de l’apprentissage. Nous menons une étude expérimentale permettant de comparer nos méthodes proposées avec les approches déjà existantes
Historically, Probabilistic Graphical Models (PGMs) are a solution for learning from uncertain and flat data, also called propositional data or attributevalue representations. In the early 2000s, great interest was addressed to the processing of relational data which includes a large number of objects participating in different relations. Probabilistic Relational Models (PRMs) present an extension of PGMs to the relational context. With the rise of the internet, numerous technological innovations and web applications are driving the dramatic increase of various and complex data. Consequently, Big Data has emerged. Several types of data stores have been created to manage this new data, including the graph databases. Recently there has been an increasing interest in graph databases to model objects and interactions. However, all PRMs structure learning use wellstructured data that are stored in relational databases. Graph databases are unstructured and schema-free data stores. Edges between nodes can have various signatures. Since, relationships that do not correspond to an ER model could be depicted in the database instance. These relationships are considered as exceptions. In this thesis, we are interested by this type of data stores. Also, we study two kinds of PRMs namely, Direct Acyclic Probabilistic Entity Relationship (DAPER) and Markov Logic Networks (MLNs). We propose two significant contributions. First, an approach to learn DAPERs from partially structured graph databases. A second approach consists to benefit from first-order logic to learn DAPERs using MLN framework to take into account the exceptions that are dropped during DAPER learning. We are conducting experimental studies to compare our proposed methods with existing approaches

Internet offre une énorme quantité d’informations à portée de main et dans une telle variété de sujets, que tout le monde est en mesure d’accéder à une énorme variété de connaissances. Une telle grande quantité d’information pourrait apporter un saut en avant dans de nombreux domaines (moteurs de recherche, réponses aux questions, tâches NLP liées) si elle est bien utilisée. De cette façon, un enjeu crucial de la communauté d’intelligence artificielle a été de recueillir, d’organiser et de faire un usage intelligent de cette quantité croissante de connaissances disponibles. Heureusement, depuis un certain temps déjà des efforts importants ont été faits dans la collecte et l’organisation des connaissances, et beaucoup d’informations structurées peuvent être trouvées dans des dépôts appelés Bases des Connaissances (BCs). Freebase, Entity Graph Facebook ou Knowledge Graph de Google sont de bons exemples de BCs. Un grand problème des BCs c’est qu’ils sont loin d’êtres complets. Par exemple, dans Freebase seulement environ 30% des gens ont des informations sur leur nationalité. Cette thèse présente plusieurs méthodes pour ajouter de nouveaux liens entre les entités existantes de la BC basée sur l’apprentissage des représentations qui optimisent une fonction d’énergie définie. Ces modèles peuvent également être utilisés pour attribuer des probabilités à triples extraites du Web. On propose également une nouvelle application pour faire usage de cette information structurée pour générer des informations non structurées (spécifiquement des questions en langage naturel). On pense par rapport à ce problème comme un modèle de traduction automatique, où on n’a pas de langage correct comme entrée, mais un langage structuré. Nous adaptons le RNN codeur-décodeur à ces paramètres pour rendre possible cette traduction
Internet provides a huge amount of information at hand in such a variety of topics, that now everyone is able to access to any kind of knowledge. Such a big quantity of information could bring a leap forward in many areas if used properly. This way, a crucial challenge of the Artificial Intelligence community has been to gather, organize and make intelligent use of this growing amount of available knowledge. Fortunately, important efforts have been made in gathering and organizing knowledge for some time now, and a lot of structured information can be found in repositories called Knowledge Bases (KBs). A main issue with KBs is that they are far from being complete. This thesis proposes several methods to add new links between the existing entities of the KB based on the learning of representations that optimize some defined energy function. We also propose a novel application to make use of this structured information to generate questions in natural language

Le Canada figure parmi les rares pays à avoir une stratégie d'interdiction de facto de fusions entre grandes banques nationales. D'un côté, dans le contexte d'une crise financière cela semble un grand atout stratégique. Par contre, les banques canadiennes sont aussi moins compétitives ou moins agressives pour promouvoir l'entrepreneurship et par conséquent, cela freine le rythme de l'innovation (Groupe d'études stratégiques sur la concurrence, 2008). Ainsi, un tel environnement financier conservateur fait souvent l'objet de critiques envers les petites et moyennes entreprises, lesquelles considèrent que les banques canadiennes ne sont pas très relationnelles. Dernièrement, la crise fInancière américaine qui a dégénéré en crise mondiale a illustré 1) les désavantages de collaborer en écosystème ouvert dans le secteur financier et 2) l'importance de réglementer et d'établir des normes rigides. Cette crise semble donc a priori conforter le conservatisme et la réglementation. Or, l'industrie des technologies de l'information et des communications (TIC) semble illustrer le contraire. En effet, pour assurer le développement de cette industrie, certains facteurs doivent être considérés: 1) l'importance de fonctionner en écosystème ouvert pour démocratiser l'innovation (Von Hippel, 2005) et, en particulier, l'innovation non contractuelle (Olleros, 2007) et 2) d'établir des normes de collaboration ou des normes relationnelles (Macneil, 2000) pour une meilleure performance économique globale (Chesbrough, 2003). Il semble que la comparaison des deux secteurs (bancaire et TIC) permet de relever la problématique relationnelle dans des contextes différents tout en aboutissant aux constats suivants: davantage de conservatisme et de réglementation permettent probablement de protéger des industries bien établies, mais cela semble freiner l'entrepreneuriat et l'innovation qui sont une source de développement économique. Ainsi, bien que le conservatisme et la réglementation soient des solutions à court terme, elles ne procurent pas le dynamisme nécessaire pour relancer et donner confiance dans les échanges socioéconomiques. Cette thèse propose de puiser au coeur d'une problématique souvent effleurée, mais non réellement élaborée parce qu'elle remet en question le fondement des échanges économiques dans un système libéral: le système de valeurs. En effet, les acteurs socio-économiques ont besoin de fonctionner selon des normes relationnelles, plutôt que transactionnelles (Macneil, 2000; Ferguson, Paulin et Bergeron, 2005) pour une meilleure performance individuelle et globale de l'écosystème (Iansiti et Levien, 2004) et avoir ainsi une logique de confiance et d'engagement de long terme (Morgan et Hunt, 1994). Ces postulats répondent à la logique du marketing relationnel dont la définition est de plus en plus sociale et systémique (Gummesson, 1999, p. 24) et intègre depuis 2004, la logique à dominance service (LDS) qui focalise sur l'importance du service comme processus de cocréation de valeur (Vargo et Lusch, 2004; 2008a; 2008b). Comment donc appliquer le marketing relationnel ou sa dernière variante, la LDS dans une perspective plus large, plus systémique et qui reflète la complexité des dyades interactionnelles? Comment rétablir le credo (Je crois dans l'avenir, McCraw, 2007, p.6) dans l'économie pour que les différents acteurs socio-économiques accordent les crédits financiers, politiques et culturels nécessaires? L'incertitude étant un point central dans la théorie transactionnelle (Williamson, 1979), il est possible de la juguler avec des normes relationnelles (Ferguson et Paulin, 2009) qui s'étendent du coeur de métier de l'industrie aux dimensions périphériques de l'écosystème global. À travers une méthodologie par articles, cette thèse explore la dynamique relationnelle dans une perspective écosystémique. Cette perspective est originale et pertinente, car elle permet: (1) d'adopter une conceptualisation appropriée des relations (théorie ancrée) selon la métaphore de l'écosystème; (2) elle saisit la réalité dans sa complexité et en temps réel (étude qualitative longitudinale); et (3) elle explore les interactions, les réseaux et les relations selon une logique systémique de contenu (les dimensions explicatives) et de processus (évolution dans le temps). Deux industries stratégiques ont été analysées: le secteur bancaire et celui des technologies de l'information et des communications. La richesse, la pertinence et la complémentarité de leurs écosystèmes ont permis de développer une compréhension triangulée des relations au sein d'un écosystème, sur les meilleures pratiques managériales et les facteurs clés de succès. L'intégration du paradigme relationnel s'est faite à trois niveaux: coeur de métier, entreprise élargie et écosystémique (Moore, 1996, p. 26). Cet objectif à trois volets a beaucoup contribué au choix de procéder à une thèse par articles. Les trois perspectives gagnaient à être explorées séparément dans trois recherches spécifiques. (1) La première a visé le coeur de métier pour apprécier les processus organisationnels relationnels mis en place avec les clients internes (directeurs de compte). (2) La deuxième recherche a ciblé l'évaluation du paradigme relationnel dans la dyade entreprise/clients organisationnels (PME) selon une vision gagnant-gagnant organisation-clients-employés. (3) La troisième recherche a focalisé sur la dynamique relationnelle coopétitive animant les dyades complexes au niveau écosystémique. D'un point de vue théorique, cette thèse propose deux contributions majeures: 1) une revue de littérature intégrative pluridisciplinaire du marketing relationnel en lien avec les nouveaux paradigmes émergents dans les autres domaines et 2) le développement d'une nouvelle théorie de l'écosystème en lien avec les défis empiriques, théoriques et méthodologiques actuels. Cette thèse illustre également l'importance de retrouver le credo dans l'économie, non pas en limitant les crédits, mais en s'assurant de partager des valeurs relationnelles durables de confiance et d'engagement au profit de l'ensemble de l'écosystème. Elle propose donc une nouvelle théorie de l'écosystème, qui est une extension du marketing relationnel et de la logique à dominance service (Vargo et Lusch, 2004; 2008a; 2008b). La LDS dénonce les pratiques marketing ancrées dans la logique industrielle de production et qui ont transformé le concept de «servuction du client» (Langeard et Eiglier, 1987) en servitude du client (Paulin, 2009). La théorie de l'écosystème proposée vient donc endosser les postulats de la LDS et les enrichir de dimensions sociales, durables et éthiques applicables à l'ensemble de l'écosystème et non pas dans une logique dyadique microscopique. D'un point de vue méthodologique, l'innovation est substantielle en termes d'approche qualitative plurielle. La triangulation est multiple: théories, disciplines, sources, méthodes de collecte, d'analyse et stratégies de théorisations. Plusieurs chercheurs en marketing ou en management ont multiplié les méta-analyses, mais les recherches quantitatives se sont concentrées soit sur le niveau micro, mezzo ou macro d'une relation. Il semble qu'aucune recherche n'a, jusqu'à présent, entrepris dans un même temps une méthodologie à la fois dyadique, systémique, dynamique et processuelle sur deux ou trois niveaux écosystémiques ou appliqué la théorie ancrée (Glaser et Strauss, 1967) pour comprendre les questions relationnelles. D'un point de vue épistémologique, cette thèse a pour principale contribution, un positionnement post moderniste de réconciliation des paradigmes. Ce dernier a permis de relever plusieurs défis d'approches de la complexité et ensuite de théorisation qui auraient été difficilement réussis en suivant des paradigmes isolés. Le dialogue interparadigmes a permis de saisir les différentes facettes de l'iceberg et d'enrichir les descriptions et explications. D'un point de vue managérial, les contributions sont aussi importantes et se situent à trois niveaux: l) un niveau dyadique client interne/organisation; 2) un niveau dyadique client externe/organisation et enfin, 3) un niveau multidyadique entre divers partenaires et notamment les compétiteurs/coopérateurs (coopétiteurs, Brandenburger et Nalebuff, 1996, p. 2). La théorie de l'écosystème proposée dans cette thèse offre donc d'être un cadre théorique, un cadre méthodologique et un cadre empirique en symbiose avec la complexité relatiormelle des écosystèmes actuels.

La compréhension des pathologies humaines et du mode d'action des médicaments passe par la prise en compte des réseaux d'interactions entre biomolécules. Les recherches récentes sur les systèmes biologiques produisent de plus en plus de données sur ces réseaux qui gouvernent les processus cellulaires. L'hétérogénéité et la multiplicité de ces données rendent difficile leur intégration dans les raisonnements des utilisateurs. Je propose ici des approches intégratives mettant en oeuvre des techniques de gestion de données, de visualisation de graphes et de fouille de données, pour tenter de répondre au problème de l'exploitation insuffisante des données sur les réseaux dans la compréhension des phénotypes associés aux maladies génétiques ou des effets secondaires des médicaments. La gestion des données sur les protéines et leurs propriétés est assurée par un système d'entrepôt de données générique, NetworkDB, personnalisable et actualisable de façon semi-automatique. Des techniques de visualisation de graphes ont été couplées à NetworkDB pour utiliser les données sur les réseaux biologiques dans l'étude de l'étiologie des maladies génétiques entrainant une déficience intellectuelle. Des sous-réseaux de gènes impliqués ont ainsi pu être identifiés et caractérisés. Des profils combinant des effets secondaires partagés par les mêmes médicaments ont été extraits de NetworkDB puis caractérisés en appliquant une méthode de fouille de données relationnelles couplée à Network DB. Les résultats permettent de décrire quelles propriétés des médicaments et de leurs cibles (incluant l'appartenance à des réseaux biologiques) sont associées à tel ou tel profil d'effets secondaires
The understanding of human diseases and drug mechanisms requires today to take into account molecular interaction networks. Recent studies on biological systems are producing increasing amounts of data. However, complexity and heterogeneity of these datasets make it difficult to exploit them for understanding atypical phenotypes or drug side-effects. This thesis presents two knowledge-based integrative approaches that combine data management, graph visualization and data mining techniques in order to improve our understanding of phenotypes associated with genetic diseases or drug side-effects. Data management relies on a generic data warehouse, NetworkDB, that integrates data on proteins and their properties. Customization of the NetworkDB model and regular updates are semi-automatic. Graph visualization techniques have been coupled with NetworkDB. This approach has facilitated access to biological network data in order to study genetic disease etiology, including X-linked intellectual disability (XLID). Meaningful sub-networks of genes have thus been identified and characterized. Drug side-effect profiles have been extracted from NetworkDB and subsequently characterized by a relational learning procedure coupled with NetworkDB. The resulting rules indicate which properties of drugs and their targets (including networks) preferentially associate with a particular side-effect profile

Configurer une expérience PHE (Physique des Hautes Energies) devient de plus en plus complexe : le nombre de modules augmente et de nouvelles technologies sont utilisées. Anticiper les fautes d’un software ou d’un hardware nécessite un système de contrôle robuste. Les systèmes autonomes et dynamiques ont été introduits récemment dans le monde PHE afin d’améliorer la robustesse des expériences. L’architecture du système de contrôle de LHCb qui intègre des outils autonomes et dynamiques (autonomique) constitue une innovation. La contribution de cette thèse est l’implémentation d’une architecture 3 tiers « autonomic » permettant de configurer l’expérience LHCb, i. E. Un gigantesque réseau d’équipement. Chaque couche a été testée et validée. Le fonctionnement de l’architecture globale et son intégration dans le système de contrôle ont été validés avec succès.

Les systèmes d'information (S.I.) d'entreprise se construisent à partir de progiciels configurés, intégrés et déployés dans des organisations en mouvement, à l'exemple des ERP ( Enterprise Resource Planning). Les enjeux d'efficacité des projets, d'efficience des usages, de performances opérationnelles, d'alignement aux stratégies d'entreprise sont connus. Ils fondent la problématique de l'intégration organisationnelle et informationnelle, avec la généricité nécessaire à la diffusion des bonnes pratiques et normes, dans une démarche continue mêlant analyse de l'existant, conception et mise en oeuvre par l'organisation. Un cadre d'ingénierie dirigée par les modèles se diffuse progressivement à partir des travaux en modélisation d'entreprise et en système d'information. Ce mémoire propose une approche centrée sur l'intégration organisationnelle et informationnelle afin d'enrichir ce cadre dans les phases de conception, d'intégration et d'usage pour prendre en compte les interdépendances entre les éléments d'un système et entre les points de vue différents sur ce système. Ce cadre étendu repose sur un méta-modèle de l'intégration et une démarche d'alignement entre les points de vue. Il s'appuie sur la théorie des graphes pour définir une « distance » et un « voisinage » permettant de représenter les différentes formes d'intégration qui conditionnent, permettent ou limitent les résultats des projets. L'analyse de différents cas issus de référentiels métiers permet de valider la pertinence du cadre proposé pour enrichir les représentations de ces modèles.

Cette thèse est consacrée à l'évaluation de requêtes logiques du point de vue de l'énumération. Nous étudions quatre classes de requêtes. En premier lieu, nous nous intéressons aux formules conjonctives acycliques avec inégalités pour lesquelles nous améliorons un résultat de Papadimitriou et Yannakakis en montrant que de telles requêtes logiques peuvent être évaluées à délai linéaire en la taille de la structure. Nous exhibons ensuite la sous-classe des formules connexe-acycliques pour lesquelles l'évaluation de requêtes s'effectue à délai constant après prétraitement linéaire. Nous montrons que cette classe est maximale pour ce résultat dans le sens suivant: si le produit de matrices booléennes ne peut pas être calculé en temps linéaire alors toute requête conjonctive acyclique est évaluable à délai constant après prétra itement linéaire si et seulement si elle est connexe-acyclique. En second lieu, nous démontrons que toute requête MSO sur une classe de structures de largeur arborescente bornée peut être évaluée à délai linéaire en la taille de chaque solution produite après un prétraitement linéaire en la taille de la structure. En troisième lieu, nous montrons que, pour chaque requête en logique du premier ordre sur des structures de degré borné, il est possible de trouver en temps constant la j-ème solution dans un certain ordre après un prétraitement linéraire. Enfin, nous établissons que les graphes d'intervalles unitaires ont une largeur de clique localement bornée. D'où nous déduisons que tout énoncé du premier ordre sur ces graphes est décidable en temps linéaire; là encore, nous démontrons une certaine maximalité de ce résultat.

La compréhension des pathologies humaines et du mode d'action des médicaments passe par la prise en compte des réseaux d'interactions entre biomolécules. Les recherches récentes sur les systèmes biologiques produisent de plus en plus de données sur ces réseaux qui gouvernent les processus cellulaires. L'hétérogénéité et la multiplicité de ces données rendent difficile leur intégration dans les raisonnements des utilisateurs. Je propose ici des approches intégratives mettant en œuvre des techniques de gestion de données, de visualisation de graphes et de fouille de données, pour tenter de répondre au problème de l'exploitation insuffisante des données sur les réseaux dans la compréhension des phénotypes associés aux maladies génétiques ou des effets secondaires des médicaments. La gestion des données sur les protéines et leurs propriétés est assurée par un système d'entrepôt de données générique, NetworkDB, personnalisable et actualisable de façon semi-automatique. Des techniques de visualisation de graphes ont été couplées à NetworkDB pour utiliser les données sur les réseaux biologiques dans l'étude de l'étiologie des maladies génétiques entrainant une déficience intellectuelle. Des sous-réseaux de gènes impliqués ont ainsi pu être identifiés et caractérisés. Des profils combinant des effets secondaires partagés par les mêmes médicaments ont été extraits de NetworkDB puis caractérisés en appliquant une méthode de fouille de données relationnelles couplée à Network DB. Les résultats permettent de décrire quelles propriétés des médicaments et de leurs cibles (incluant l'appartenance à des réseaux biologiques) sont associées à tel ou tel profil d'effets secondaires.

Les travaux de recherche exposes dans ce memoire relevent du domaine de l'informatique documentaire, et se situent plus particulierement parmi les travaux sur les systemes intelligents en recherche d'informations. Notre etude s'inscrit dans le prolongement du projet infodiab, qui est un systeme de recherche d'informations utilisant le langage courant comme source d'informations et comme moyen d'interrogation. Ce systeme est destine a faciliter la prise en charge d'une maladie grave et contraignante: le diabete. Notre premiere contribution a permis le couplage de infodiab avec le systeme dialog (une messagerie et un forum) que nous avons developpe dans le but de favoriser le dialogue entre les patients diabetiques et leur medecin generaliste, mais egalement afin de pouvoir mettre a jour le fonds documentaire du systeme de recherche d'informations, et ceci principalement en fonction des besoins en informations des utilisateurs. Notre deuxieme contribution a pour but la realisation d'un systeme de recherche d'informations base sur un modele de representation qui s'inspire de la theorie des graphes conceptuels en reprenant les grands principes. La structure utilisee pour representer la connaissance est un graphe oriente assimilable a un graphe conceptuel que nous avons appele graphe syntaxique. L'interet de notre approche est de gerer la syntaxe et la semantique utiles et representatives dans le domaine de l'application pour la representation des documents et l'evaluation des requetes, et ceci afin d'obtenir un modele de representation suffisamment simple pour permettre une manipulation efficace. Par rapport aux systemes de recherche classiques, notre systeme offre tout d'abord une meilleure comprehension des documents et des requetes. Ceci se traduit par une reconnaissance des relations syntaxiques et semantiques entre les termes d'un document ou d'une requete. De plus, notre systeme permet une comparaison intelligente entre un document et une requete, ce qui signifie en fait l'utilisation des connaissances syntaxiques et semantiques entre les differents termes durant l'evaluation d'une requete. Ainsi, cela contribue a ameliorer le taux de rappel et le taux de precision du systeme

Cette these presente des travaux qui s'inscrivent dans le cadre de l'informatique linguistique et plus precisement dans le domaine de l'extraction de connaissances a partir de textes. Notre but est d'aller au-dela de l'indexation classique par mots-cles en representant l'information retenue comme pertinente sous une forme structuree. Ce projet a fait l'objet d'une collaboration avec la direction des etudes et des recherches d'edf. Pour representer le contenu semantique de textes rediges sans contrainte d'expression, nous avons distingue trois niveaux d'analyse: le niveau pragmatique, le niveau linguistique et le niveau conceptuel. Le niveau pragmatique permet le decoupage d'un texte selon ses parties rhetoriques qui correspondent a des articulations. Le niveau linguistique consiste a structurer les fragments de phrases pertinents pour chaque articulation sous la forme de structures predicatives etiquetees par des roles thematiques precis. Enfin, le niveau conceptuel vise a ameliorer la qualite d'exploitation des resultats du niveau linguistique, notamment en vue de l'interrogation de bases documentaires. Apres analyse de differentes approches, nous avons retenu la lcs (structure lexicale conceptuelle), theorie de jackendoff, pour representer conceptuellement les predicats consideres. Notre contribution sur le plan linguistique a consiste en un travail en profondeur sur la definition de l'ensemble des ressources linguistiques necessaires aux differentes etapes d'analyse que nous avons identifiees. Nous avons notamment defini un ensemble de roles thematiques qio ont une dimension cognitive et un certain nombre de donnees supplementaires en relation avec la lcs (primitives, etc. ). Nous avons aussi caracterise des elements de methode pour la definition de ressources lcs specifiques a un corpus donne. Nos analyses ont ete validees par la mise en uvre du prototype papins (prototype d'analyse pour la production d'index semantiques) que nous avons developpe en prolog

Cette dernière décennie, la modélisation des villes 3D est devenue l'un des enjeux de la recherche multimédia et un axe important en reconnaissance d'objets. Dans cette thèse nous nous sommes intéressés à localiser différentes primitives, plus particulièrement les fenêtres, dans les façades de Paris. Dans un premier temps, nous présentons une analyse des façades et des différentes propriétés des fenêtres. Nous en déduisons et proposons ensuite un algorithme capable d'extraire automatiquement des hypothèses de fenêtres. Dans une deuxième partie, nous abordons l'extraction et la reconnaissance des primitives à l'aide d'appariement de graphes de contours. En effet une image de contours est lisible par l'oeil humain qui effectue un groupement perceptuel et distingue les entités présentes dans la scène. C'est ce mécanisme que nous avons cherché à reproduire. L'image est représentée sous la forme d'un graphe d'adjacence de segments de contours, valué par des informations d'orientation et de proximité des segments de contours. Pour la mise en correspondance inexacte des graphes, nous proposons plusieurs variantes d'une nouvelle similarité basée sur des ensembles de chemins tracés sur les graphes, capables d'effectuer les groupements des contours et robustes aux changements d'échelle. La similarité entre chemins prend en compte la similarité des ensembles de segments de contours et la similarité des régions définies par ces chemins. La sélection des images d'une base contenant un objet particulier s'effectue à l'aide d'un classifieur SVM ou kppv. La localisation des objets dans l'image utilise un système de vote à partir des chemins sélectionnés par l'algorithme d'appariement
This last decade, modeling of 3D city became one of the challenges of multimedia search and an important focus in object recognition. In this thesis we are interested to locate various primitive, especially the windows, in the facades of Paris. At first, we present an analysis of the facades and windows properties. Then we propose an algorithm able to extract automatically window candidates. In a second part, we discuss about extraction and recognition primitives using graph matching of contours. Indeed an image of contours is readable by the human eye, which uses perceptual grouping and makes distinction between entities present in the scene. It is this mechanism that we have tried to replicate. The image is represented as a graph of adjacency of segments of contours, valued by information orientation and proximity to edge segments. For the inexact matching of graphs, we propose several variants of a new similarity based on sets of paths, able to group several contours and robust to scale changes. The similarity between paths takes into account the similarity of sets of segments of contours and the similarity of the regions defined by these paths. The selection of images from a database containing a particular object is done using a KNN or SVM classifier