Cette thèse porte sur la fouille de graphes et propose un ensemble de méthodes pour la découverte de contrastes entre classes et leurs contributions à des problématiques de prédictions de propriétés (éco)toxicologiques de composés chimiques. Nous présentons un nouveau type de motifs, les motifs émergents de graphes - les conjonctions de graphes dont la présence est liée à la classification donnée en entrée - afin de cibler l'information caractérisant les différentes lasses. Notre méthode repose sur un changement de description des graphes permettant de revenir à un contexte de fouille de données tabulaires. L'étendue des contraintes utilisées en fouille de données tabulaires peut ainsi être exploitée, telle que la contrainte d'émergence. Nous montrons également qu'il est possible d'étendre aux motifs de graphes les représentations condensées de motifs sur la contrainte d'émergence. Cette méthode synthétise les motifs de graphes et facilite leur exploration et leur usages. Le fil conducteur de ce travail est celui de l'évaluation de propriétés (éco)toxicologiques de molécules par l'usage de modèles in silico, conformément à la norme européenne REACH. Dans ce contexte, les méthodes de fouille de graphes proposées permettent d'extraire des toxicophores (i.e. des fragments de molécules qui peuvent influencer le comportement toxique des molécules) à partir des exemples d'une chimiothèque. Une série expérimentale montre l'apparition de nouvelles structures lorsque le niveau de toxicité des molécules augmente. Ces travaux contribuent à l'acquisition de nouvelles connaissances sur les mécanismes de toxicité des molécules venant compléter les connaissances expertes humaines.

Dans les bibliothèques et les médiathèques, une caractéristique importante des fonds documentaires mis à disposition est qu'ils contiennent d'abondantes références a l'histoire, à la géographie, au patrimoine, en somme au territoire, et il est primordial pour ces centres de valoriser ces spécificités territoriales pour répondre à des objectifs d'information et d'éducation. Dans ce contexte, nous faisons l'hypothèse qu'en utilisant un point de vue géographique pour mod eliser un ensemble de ressources terminologiques utilisées pour indexer un fond documentaire, il est possible de faire émerger une représentation du territoire qui y est implicitement décrite. Concernant la modélisation de la connaissance en géomatique, de nombreux travaux s'appliquent à construire une représentation sémantique structurée géographique de domaines cibles. Cependant, il ne semble pas exister d'approche permettant de construire une représentation d'un territoire à partir de fonds documentaires annotés. Nous proposons donc une méthodologie complète et automatisée permettant de construire une couche conceptuelle de type ontologie d'un territoire, sur la base d'un fonds documentaire indexé par des experts. Nous positionnons nos travaux dans l'extraction et la structuration de la connaissance que nous appliquons dans le domaine de la géomatique en nous appuyant notamment sur des techniques provenant du Traitement Automatique du Langage Naturel. Nous entendons ici par territoire un ensemble de lieux que l'on peut mettre en relation selon un ensemble de thèmes en fonction d'une période donnée. Ainsi, nous présentons un complément original s'appuyant sur le travail d'indexation réalisé par les experts documentalistes sur un fonds documentaire pour faire émerger une ontologie d'un territoire implicitement décrit dans les documents. Une contribution importante de notre travail concerne l'enrichissement de fa con incrémentale de la représentation d'un territoire. Nous proposons pour cela une chaine de TALN qui permet de marquer dans des documents textes annotés un ensemble d'informations spatiales, temporelles et thématiques qui nous sert de base pour l'enrichissement de la représentation d'un territoire. Une perspective à ces travaux est de pouvoir valider notre approche sur plusieurs fonds documentaires d'origines diverses. L'intérêt sera de proposer une méthode qui, sur la base des représentations de territoires obtenues, permettrait d'identifier et de représenter les spécificités de chaque fonds documentaire.

Les technologies de traduction automatique existantes sont à présent vues comme une approche prometteuse pour aider à produire des traductions de façon efficace et à coût réduit. Cependant, l'état de l'art actuel ne permet pas encore une automatisation complète du processus et la coopération homme/machine reste indispensable pour produire des résultats de qualité. Une pratique usuelle consiste à post-éditer les résultats fournis par le système, c'est-à-dire effectuer une vérification manuelle et, si nécessaire, une correction des sorties erronées du système. Ce travail de post-édition effectué par les utilisateurs sur les résultats de traduction automatique constitue une source de données précieuses pour l'analyse et l'adaptation des systèmes. La problématique abordée dans nos travaux s'intéresse à développer une approche capable de tirer avantage de ces retro-actions (ou post-éditions) d'utilisateurs pour améliorer, en retour, les systèmes de traduction automatique. Les expérimentations menées visent à exploiter un corpus d'environ 10 000 hypothèses de traduction d'un système probabiliste de référence, post-éditées par des volontaires, par le biais d'une plateforme en ligne. Les résultats des premières expériences intégrant les post-éditions, dans le modèle de traduction d'une part, et par post-édition automatique statistique d'autre part, nous ont permis d'évaluer la complexité de la tâche. Une étude plus approfondie des systèmes de post-éditions statistique nous a permis d'évaluer l'utilisabilité de tels systèmes ainsi que les apports et limites de l'approche. Nous montrons aussi que les post-éditions collectées peuvent être utilisées avec succès pour estimer la confiance à accorder à un résultat de traduction automatique. Les résultats de nos travaux montrent la difficulté mais aussi le potentiel de l'utilisation de post-éditions d'hypothèses de traduction automatiques comme source d'information pour améliorer la qualité des systèmes probabilistes actuels.

Certaines applications du traitement automatique des langues sont amenées à traiter des flux de données textuelles caractérisés par l'emploi d'un vocabulaire en perpétuelle évolution, que ce soit au niveau de la création des mots que des sens de ceux existant déjà. En partant de ce constat, nous avons mis au point un algorithme incrémental pour construire automatiquement et faire évoluer une base lexicale qui répertorie des unités lexicales non étiquetées sémantiquement observées dans des flux. Cette base lexicale est représentée par un treillis de Galois qui organise des concepts formels (assimilés à des unités de sens) sur des niveaux de granularité allant du très spécifique au très général. Cette représentation est complétée par une modélisation vectorielle visualisable qui tient compte des aspects continus du sens et de la proximité sémantique entre concepts. Ce modèle est alors exploité pour propager l'étiquetage manuel d'un petit nombre d'entités nommées (EN : unités lexicales qui se référent habituellement à des personnes, des lieux, des organisations...) à d'autres EN non étiquetées observées dans un flux pendant la construction incrémentale du treillis. Les concepts de ce treillis sont enrichis avec les étiquettes d'EN observées dans un corpus d'apprentissage. Ces concepts et leurs étiquettes attachées sont respectivement employés pour l'annotation non supervisée et la classification supervisée des EN d'un corpus de test.

L'extraction de connaissances à partir de données incomplètes constitue un axe de recherche en plein essor. Dans cette thèse, nous y contribuons par la proposition d'une méthode de complétion des valeurs manquantes. Nous commençons par aborder cette problématique par la définition de modèles d'apparition des valeurs manquantes. Nous en proposons une nouvelle typologie en fonction des données connues et nous les caractérisons de façon non redondante grâce à la base d'implications propres. Un algorithme de calcul de cette base de règles, formalisé à partir de la théorie des hypergraphes, est également proposé dans cette thèse. Ensuite, nous exploitons les informations fournies lors de l'étape de caractérisation afin de proposer une méthode de complétion contextualisée, qui complète les valeurs manquantes selon le type aléatoire/non-aléatoire et selon le contexte. La complétion des valeurs manquantes non aléatoires est effectuée par des valeurs spéciales, renfermant intrinsèquement les origines des valeurs manquantes et déterminées grâce à des schémas de caractérisation. Finalement, nous nous intéressons aux techniques d'évaluation des méthodes de complétion et nous proposons une nouvelle technique fondée sur la stabilité d'un clustering entre les données de référence et les données complétées.

Québec Université Laval, Bibliothèque 2016

This thesis suggests the use of tools from the disciplines of Computational Linguistics and Knowledge Representation with the idea that such tools would enable the partial automation of two processes of Conceptual Design: the analysis of Requirements and the synthesis of concepts of solution. The viewpoint on Conceptual Design developed in this research is based on the systematic methodologies developed in the literature. The evolution of these methodologies provided precise description of the tasks to be achieved by the designing team in order to achieve successful design. Therefore, the argument of this thesis is that it is possible to create computer models of some of these tasks in order to partially automate the refinement of the design problem and the exploration of the design space. In Requirements Engineering, the definition of requirements consists in identifying the needs of various stakeholders and formalizing it into design speciႡcations. During this task, designers face the problem of having to deal with individuals from different expertise, expressing their needs with different levels of clarity. This research tackles this issue with requirements expressed in natural language (in this case in English). The analysis of needs is realised from different linguistic levels: lexical, syntactic and semantic. The lexical level deals with the meaning of words of a language. Syntactic analysis provides the construction of the sentence in language, i.e. the grammar of a language. The semantic level aims at Ⴁnding about the specific meaning of words in the context of a sentence. This research makes extensive use of a semantic atlas based on the concept of clique from graph theory. Such concept enables the computation of distances between a word and its synonyms. Additionally, a methodology and a metric of similarity was defined for clarifying requirements at syntactic, lexical and semantic levels. This methodology integrates tools from research collaborators. In the synthesis process, a Knowledge Representation of the necessary concepts for enabling computers to create concepts of solution was developed. Such, concepts are: function, input/output Ⴂow, generic organs, behaviour, components. The semantic atlas is also used at that stage to enable a mapping between functions and their solutions. It works as the interface between the concepts of this Knowledge Representation.

Nucleotide sequence alignment is a method used to identify regions of similarity between organisms at the genomic level. In this thesis we focus on the alignment of millions of short sequences produced by Next-Generation Sequencing (NGS) technologies against a reference database. Particularly, we direct our attention toward the analysis of metagenomic and metatranscriptomic data, that is the DNA and RNA directly extracted for an environment. Two major challenges were confronted in our developed algorithms. First, all NGS technologies today are susceptible to sequencing errors in the form of nucleotide substitutions, insertions and deletions and error rates vary between 1-15%. Second, metagenomic samples can contain thousands of unknown organisms and the only means of identifying them is to align against known closely related species. To overcome these challenges we designed a new approximate matching technique based on the universal Levenshtein automaton which quickly locates short regions of similarity (seeds) between two sequences allowing 1 error of any type. Using seeds to detect possible high scoring alignments is a widely used heuristic for rapid sequence alignment, although most existing software are optimized for performing high similarity searches and apply exact seeds. Furthermore, we describe a new indexing data structure based on the Burst trie which optimizes the search for approximate seeds. We demonstrate the efficacy of our method in two implemented software, SortMeRNA and SortMeDNA. The former can quickly filter ribosomal RNA fragments from metatranscriptomic data and the latter performs full alignment for genomic and metagenomic data.

Les corpus, collections de textes sélectionnés dans un objectif spécifique, occupent une place de plus en plus déterminante en Linguistique comme en Traitement Automatique des Langues (TAL). Considérés à la fois comme source de connaissances sur l'usage authentique des langues, ou sur les entités que désignent des expressions linguistiques, ils sont notamment employés pour évaluer la performance d'applications de TAL. Les critères qui prévalent à leur constitution ont un impact évident, mais encore délicat à caractériser, sur (i) les structures linguistiques majeures qu'ils renferment, (ii) les connaissances qui y sont véhiculées, et, (iii) la capacité de systèmes informatiques à accomplir une tâche donnée. Ce mémoire étudie des méthodologies d'extraction automatique de relations sémantiques dans des corpus de textes écrits. Un tel sujet invite à examiner en détail le contexte dans lequel une expression linguistique s'applique, à identifier les informations qui déterminent son sens, afin d'espérer relier des unités sémantiques. Généralement, la modélisation du contexte est établie à partir de l'analyse de co-occurrence d'informations linguistiques issues de ressources ou obtenues par des systèmes de TAL. Les intérêts et limites de ces informations sont évalués dans le cadre de la tâche d'extraction de relations sur des corpus de genre différent (article de presse, conte, biographie). Les résultats obtenus permettent d'observer que pour atteindre une représentation sémantique satisfaisante ainsi que pour concevoir des systèmes robustes, ces informations ne suffisent pas. Deux problèmes sont particulièrement étudiés. D'une part, il semble indispensable d'ajouter des informations qui concernent le genre du texte. Pour caractériser l'impact du genre sur les relations sémantiques, une méthode de classification automatique, reposant sur les restrictions sémantiques qui s'exercent dans le cadre de relations verbo-nominales, est proposée. La méthode est expérimentée sur un corpus de conte et un corpus de presse. D'autre part, la modélisation du contexte pose des problèmes qui relèvent de la variation discursive de surface. Un texte ne met pas toujours bout à bout des expressions linguistiques en relation et il est parfois nécessaire de recourir à des algorithmes complexes pour détecter des relations à longue portée. Pour répondre à ce problème de façon cohérente, une méthode de segmentation discursive, qui s'appuie sur des indices de structuration de surface apparaissant dans des corpus écrits, est proposée. Elle ouvre le champ à la conception de grammaires qui permettent de raisonner sur des catégories d'ordre macro-syntaxique afin de structurer la représentation discursive d'une phrase. Cette méthode est appliquée en amont d'une analyse syntaxique et l'amélioration des performances est évaluée. Les solutions proposées à ces deux problèmes nous permettent d'aborder l'extraction d'information sous un angle particulier : le système implémenté est évalué sur une tâche de correction d'Entités Nommées dans le contexte d'application des Systèmes de Question-Réponse. Ce besoin spécifique entraîne l'alignement de la définition d'une catégorie sur le type de réponse attendue par une question.

Les masses de données textuelles aujourd'hui disponibles engendrent un problème difficile lié à leur traitement automatique. Dans ce cadre, des méthodes de Fouille de Textes (FT) et de Traitement Automatique du Langage (TAL) peuvent, en partie, répondre à une telle problématique. Elles consistent à modéliser puis mettre en œuvre des méthodologies appliquées aux données textuelles afin d'en déterminer le sens et/ou découvrir des connaissances nouvelles. Dans ce processus, le descripteur linguistique constitue un élément pivot. Après une présentation des méthodes de traitement des descripteurs en eux-mêmes, ces derniers seront étudiés en contexte, c'est-à-dire en corpus. L'identification des descripteurs est souvent difficile à partir de corpus bruités et à faible contenu textuel sur lesquels nous concentrons nos efforts (par exemple, corpus issus du Web 2.0 ou du traitement OCR). Outre les mots considérés comme des descripteurs linguistiques pertinents en FT, nous nous sommes également intéressés à l'étude des syntagmes complexes à partir de corpus classiques puis d'une terminologie classique à partir de corpus complexes (par exemple, données logs ou corpus en français médiéval). Dans la suite, les syntagmes étudiés ne se situent plus à proprement parler dans les textes mais ils seront induits à partir des mots issus des corpus. Les méthodes proposées permettent de mettre en relief des syntagmes originaux tout à fait utiles pour l'identification d'Entités Nommées, le titrage automatique ou la construction de classes conceptuelles. Contrairement au raisonnement déductif, le raisonnement inductif est dit hypothétique. Dans ce cadre, l'utilisation de méthodes de validation automatique des relations induites par le biais d'approches de Fouille du Web se révèle déterminant. Les perspectives à ce travail se concentreront sur l'extraction de nouveaux descripteurs. Ces derniers seront associés à de nouvelles représentations sous forme d'entrepôts de données textuelles. Enfin, les travaux que nous souhaitons développer se focaliseront sur l'analyse des textes dans un contexte plus vaste lié au multimédia que le paradigme du Web 2.0 a mis en exergue ces dernières années.